Article
Mathematics, Applied
Xia Hong, Wei Feng
Summary: For a graph G, if there exist k spanning trees T-1, T-2, ..., T-k, such that the paths from any two vertices u, v in these k trees are pairwise openly disjoint, then these k trees are completely independent. Hasunuma proved that there are two completely independent spanning trees in any 4-connected maximal planar graph, and the problem of deciding whether there exist two completely independent spanning trees in a given graph G is NP-complete. This paper investigates the number of completely independent spanning trees in some Cartesian product graphs.
Article
Computer Science, Theory & Methods
Huanwen Zhang, Yan Wang, Jianxi Fan, Chang Shu
Summary: This paper studies the existence and construction of edge-independent spanning trees (EISTs) in the n-dimensional folded crossed cube (FC Qn), and verifies the validity of the proposed algorithm through theoretical proof and simulation experiments.
THEORETICAL COMPUTER SCIENCE
(2023)
Article
Engineering, Multidisciplinary
Kung-Jui Pai, Jinn-Shyong Yang, Guan-Yu Chen, Jou-Ming Chang
Summary: The existence of multiple completely independent spanning trees (CISTs) in a network has significant applications in fault-tolerant routing and secure message distribution. This paper proposes linear-time algorithms for constructing dual CISTs in dense Gaussian networks (DGNs) and evaluates the performance of protection routing in DGNs using simulation results.
IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING
(2022)
Article
Computer Science, Hardware & Architecture
Yifeng Wang, Baolei Cheng, Jianxi Fan, Yu Qian, Ruofan Jiang
Summary: In this paper, a general algorithm is proposed for the first time to establish the relationship between edge-disjoint spanning trees in an interconnection network and its line graph, leading to the discovery of more completely independent spanning trees. Furthermore, the lack of results regarding CISTs on line graphs is highlighted.
Article
Computer Science, Information Systems
Dun-Wei Cheng, Kai-Hsun Yao, Sun-Yuan Hsieh
Summary: The generalized recursive circulant networking can be widely applied in the design and implementation of interconnection networks, with processors connected through bidirectional, point-to-point communication channels. By applying the concept of shortest path routing to build independent spanning trees, this approach loosens previous research restrictions and extends results to a more general vertex setting using a specific algorithm to address constraint issues.
Article
Computer Science, Theory & Methods
Baolei Cheng, Dajin Wang, Jianxi Fan
Summary: This survey provides a comprehensive collection of important works on ISTs and offers a historical perspective on the development of ISTs, serving as a useful reference for future research in this field.
ACM COMPUTING SURVEYS
(2023)
Article
Mathematics
Carl Buerger, Jan Kurkofka
Summary: This paper addresses Halin's question on characterizing an important class of graphs using an ordinal function. Through investigating the normally traceable graphs, the equivalence between having a rayless spanning tree and all ends being dominated is proven, relying on a characterisation by an ordinal rank function.
JOURNAL OF GRAPH THEORY
(2022)
Article
Mathematics, Applied
Litao Guo, Gulnaz Boruzanli Ekinci
Summary: In this paper, a new type of network called folded twisted crossed cube FTCQ(n) is introduced, obtained from twisted crossed cube TCQ(n) by adding extra edges. The connectivity and edge connectivity of FTCQ(n) are shown to be n + 1 for n >= 4. Additionally, the super-connectivity and super-edge-connectivity of FTCQn are determined to be 2n for n >= 4.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Automation & Control Systems
Wei Dong, Changyang Gong, Gang Chen, Xinjun Sheng, Xiangyang Zhu
Summary: This article presents a novel topological mapping approach capable of handling multiple hypotheses with significantly improved computational efficiency at a linear time cost. By utilizing intelligent pointers to organize the correspondence between nodes and edges, loop closure judgment and inference are conducted based on spanning trees, resulting in a fast, efficient, and scalable topological mapping solution.
IEEE-ASME TRANSACTIONS ON MECHATRONICS
(2022)
Article
Automation & Control Systems
Wei Dong, Changyang Gong, Gang Chen, Xinjun Sheng, Xiangyang Zhu
Summary: This article presents a novel topological mapping approach that handles multiple hypotheses, achieving high computational efficiency with linear time complexity. The approach involves layered spanning trees, inference algorithms, and intelligent pointers to establish a storage separation of map nodes and edges. By evaluating loop closure and re-inferring hypotheses based on a Bayes-based recursive inference method, the proposed approach updates the spanning tree of map edges. Experimental results show that the approach is efficient, robust, and scalable, reducing computation and memory consumption compared to existing methods with exponential complexity.
IEEE-ASME TRANSACTIONS ON MECHATRONICS
(2022)
Article
Management
Martine Labbe, Mercedes Landete, Marina Leal
Summary: This study introduces the problem of jointly determining a set of features and a dendrogram according to the single linkage method, proposing different formulations and studying different bounds on the objective function. The effectiveness of the different models is discussed through extensive computational study, comparing the model with valid inequalities to the decomposition algorithm. The computational results also demonstrate that integrating feature selection into the optimization model allows for a satisfactory percentage of information to be preserved.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2023)
Article
Mathematics, Applied
Fengming Dong, Jun Ge, Zhangdong Ouyang
Summary: The number of spanning trees in a connected multi-graph can be calculated using the Matrix-Tree Theorem and Tutte's deletion-contraction formula, but this note presents an alternative method based on vertex degrees.
APPLIED MATHEMATICS AND COMPUTATION
(2022)
Article
Mathematics
Kung-Jui Pai
Summary: This paper discusses the applications of edge-disjoint Hamiltonian cycles (EDHC) in locally twisted cubes (FLTQ) and crossed cubes (FCQ) with the center at the origin, including parallel data broadcasting and edge fault-tolerance in network communications. Three EDHCs are constructed in FLTQ(5) and FCQ(5) using the technique of edge exchange. It is proved that there are three EDHCs in FLTQ(n) and FCQ(n) when n≥6 based on their recursive structures. The data broadcasting performance of three EDHCs in FLTQ(n) and FCQ(n) is evaluated by simulation for 5≤n≤9, considering multiple faulty edges occurring randomly.
Article
Computer Science, Hardware & Architecture
Zaid Hussain, Hosam AboElFotoh, Bader AlBdaiwi
Summary: This paper presents two efficient methods for solving the problem of finding a maximal set of independent spanning trees in Eisenstein-Jacobi networks. It also provides a distributed fault-tolerant routing algorithm based on these constructed trees. The experimental results demonstrate that the proposed method outperforms the state-of-the-art method in broadcasting in terms of node coverage.
JOURNAL OF SUPERCOMPUTING
(2022)
Article
Computer Science, Theory & Methods
Guo Chen, Baolei Cheng, Dajin Wang
Summary: This article discusses the importance and applications of constructing Completely Independent Spanning Trees (CISTs) in a network, especially in data center networks. It also introduces the augmented cube AQn as the underlying structure of a data center network and studies how to construct n-1 optimal CISTs in its logic graph L-AQDNn. Additionally, the relationship between the dimension of a hypercube-family network and the number of CISTs it can host is established for the first time.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2021)
Article
Engineering, Multidisciplinary
Kung-Jui Pai, Jinn-Shyong Yang, Guan-Yu Chen, Jou-Ming Chang
Summary: The existence of multiple completely independent spanning trees (CISTs) in a network has significant applications in fault-tolerant routing and secure message distribution. This paper proposes linear-time algorithms for constructing dual CISTs in dense Gaussian networks (DGNs) and evaluates the performance of protection routing in DGNs using simulation results.
IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING
(2022)
Article
Computer Science, Interdisciplinary Applications
Yu-Han Chen, Kung-Jui Pai, Hsin-Jung Lin, Jou-Ming Chang
Summary: Completely Independent Spanning Trees (CISTs) are a set of spanning trees used in graph theory for fault-tolerant routing and secure message distribution. A recent paper proposes an algorithm for constructing a triple CIST in a specific network structure using the CIST-partition technique. The paper also presents a recursive algorithm for constructing a triple CIST in high-dimensional networks.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Article
Computer Science, Theory & Methods
Xiao-Yan Li, Wanling Lin, Wenzhong Guo, Jou-Ming Chang
Summary: This article introduces a secure multi-protection routing scheme (SMPR-scheme) that ensures confidential data transmission and effectively resists privacy collection by extending the concept of protection routing and introducing a secure mechanism.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2022)
Article
Computer Science, Theory & Methods
Xiao-Yan Li, Wanling Lin, Ximeng Liu, Cheng-Kuan Lin, Kung-Jui Pai, Jou-Ming Chang
Summary: The paper investigates the construction of completely independent spanning trees (CISTs) in a server-centric data center network called BCube connected crossbars (BCCC) for fault-tolerant routing. The network offers good performance and reliability, with the fault-tolerant routing evaluated through simulation results.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2022)
Article
Computer Science, Hardware & Architecture
Kung-Jui Pai, Ro-Yu Wu, Sheng-Lung Peng, Jou-Ming Chang
Summary: This paper investigates the construction of multiple edge-disjoint Hamiltonian cycles (EDHCs) in a crossed cube network and evaluates the performance of data broadcasting. The results show that multiple EDHCs can be constructed in the crossed cube network, significantly improving the success rate and latency of edge fault-tolerant data broadcasting.
JOURNAL OF SUPERCOMPUTING
(2023)
Article
Mathematics, Applied
Mei-Mei Gu, Jou-Ming Chang
Summary: The neighbor connectivity and edge neighbor connectivity of a graph G refer to the minimum number of vertices and edges, respectively, that, when their closed neighborhoods are removed from G, result in an empty, complete, or disconnected graph. These two types of connectivity were derived from assessing the impact of subversion in spy networks caused by underground resistance movements. They currently provide more accurate measures of network reliability and fault-tolerance.
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Computer Science, Hardware & Architecture
Wanling Lin, Xiao-Yan Li, Jou-Ming Chang, Xiaohua Jia
Summary: The rapid growth of data center networks (DCNs) is driven by the popularity of cloud computing, data explosion, and lower setup costs, resulting in more frequent component failures. DCNs require reliable operation and efficient routing algorithms for data transmission between servers, particularly fault-tolerant routing. Constructing independent spanning trees (CISTs) has been a focus for fault-tolerant routing, and BCube-based DCN (BDCN) provides a unified framework for consistent algorithm design. This study presents the first construction of multiple CISTs in DCNs with switch failures and evaluates the performance of fault-tolerant routing through experiments using standard metrics such as average path length (APL) and transmission failure rate (TFR).
IEEE TRANSACTIONS ON COMPUTERS
(2023)
Article
Computer Science, Theory & Methods
Mei-Mei Gu, Kung-Jui Pai, Jou-Ming Chang
Summary: This paper investigates the neighbor connectivity and edge neighbor connectivity of two hierarchical networks, namely hierarchical star network H Sn and complete cubic network CCn, which use Sn and Qn as building blocks. The results show that kappa NB(H Sn) = n-1 and lambda NB(H Sn) = n for n > 3, and kappa NB(CCn) = fn21 + 1 and lambda NB (CCn) = n + 1 for n > 2.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2023)
Article
Computer Science, Theory & Methods
Shu-Li Zhao, Jou-Ming Chang
Summary: This paper investigates the generalized connectivity on the divide-and-swap cube DSCn, which has a nice hierarchical structure and plentiful properties. The result kappa 4(DSCn) = d is obtained by constructing d internally disjoint trees connecting any four arbitrary vertices of DSCn, where d = log2 n > 1. As a result, kappa 3(DSCn) = d.
THEORETICAL COMPUTER SCIENCE
(2023)
Article
Mathematics, Applied
Shu-Li Zhao, Jou -Ming Chang, Heng-Zhe Li
Summary: The generalized connectivity is a parameter that measures the capability of connecting vertices in graph G and is a generalization of traditional connectivity. The pancake graph has desirable properties for designing interconnection networks. This paper determines that the generalized 4-connectivity of the pancake graph Pn is n-2, meaning there are (n-2) internally disjoint S-trees connecting any four arbitrary vertices x, y, z, and w, where S = {x, y, z, w}. As a corollary, the generalized 3-connectivity of the pancake graph Pn can be obtained directly.
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Mathematics
Hongbin Zhuang, Jou-Ming Chang, Xiao-Yan Li, Fangying Song, Qinying Lin
Summary: This paper presents two different all-to-all broadcast algorithms for the Galaxyfly network, which adhere to the supernode-first rule and the router-first rule. Our performance evaluation validates their effectiveness, showing that the first algorithm achieves higher network channel utilization, while the second algorithm significantly reduces average collection time for routers from supernodes.
Article
Computer Science, Hardware & Architecture
Hongbin Zhuang, Xiao-Yan Li, Jou-Ming Chang, Cheng-Kuan Lin, Ximeng Liu
Summary: This article proposes the concept of the partitioned fault model and explores the fault tolerability of interconnection networks using novel indicators. The research results demonstrate the optimality of these indicators in terms of the number of edge faults tolerated.
IEEE TRANSACTIONS ON COMPUTERS
(2023)
Article
Computer Science, Information Systems
Shu-Li Zhao, Jou-Ming Chang
Summary: The article introduces the concepts of graph G and set S, defines S-tree and internally disjoint trees, and describes the definition of generalized r-connectivity and the characteristics of the folded divide-and-swap cube.
INFORMATION PROCESSING LETTERS
(2023)
Article
Computer Science, Theory & Methods
Hsin-Jung Lin, Shyue-Ming Tang, Kung-Jui Pai, Jou-Ming Chang
Summary: This paper investigates the problem of constructing a dual-CIST in the n-dimensional hierarchical folded cubic network HFQn. A recursive algorithm is proposed to construct a dual-CIST of HFQ(n) in O(22(n)) time for n=2, where the time required is the same scale as the number of vertices of HFQ(n). Also, the diameter of each constructed CIST is 4n + 1.
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
(2023)
Article
Computer Science, Theory & Methods
Hongbin Zhuang, Xiao-Yan Li, Jou-Ming Chang, Dajin Wang
Summary: This paper proposes an efficient fault-tolerant Hamiltonian path embedding algorithm for enhancing the fault-tolerant capacity of k-ary n-cubes. A new conditional fault model named Partitioned Edge Fault model (PEF model) is introduced. Experimental and comparative results show that the algorithm significantly improves the edge fault tolerance compared to known results.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2023)
Article
Computer Science, Information Systems
Xia Liang, Jie Guo, Peide Liu
Summary: This paper investigates a novel consensus model based on social networks to manage manipulative and overconfident behaviors in large-scale group decision-making. By proposing a novel clustering model and improved methods, the consensus reaching is effectively facilitated. The feedback mechanism and management approach are employed to handle decision makers' behaviors. Simulation experiments and comparative analysis demonstrate the effectiveness of the model.
INFORMATION SCIENCES
(2024)
Article
Computer Science, Information Systems
Xiang Li, Haiwang Guo, Xinyang Deng, Wen Jiang
Summary: This paper proposes a method based on class gradient networks for generating high-quality adversarial samples. By introducing a high-level class gradient matrix and combining classification loss and perturbation loss, the method demonstrates superiority in the transferability of adversarial samples on targeted attacks.
INFORMATION SCIENCES
(2024)
Article
Computer Science, Information Systems
Lingyun Lu, Bang Wang, Zizhuo Zhang, Shenghao Liu
Summary: Many recommendation algorithms only rely on implicit feedbacks due to privacy concerns. However, the encoding of interaction types is often ignored. This paper proposes a relation-aware neural model that classifies implicit feedbacks by encoding edges, thereby enhancing recommendation performance.
INFORMATION SCIENCES
(2024)
Article
Computer Science, Information Systems
Jaehong Yu, Hyungrok Do
Summary: This study discusses unsupervised anomaly detection using one-class classification, which determines whether a new instance belongs to the target class by constructing a decision boundary. The proposed method uses a proximity-based density description and a regularized reconstruction algorithm to overcome the limitations of existing one-class classification methods. Experimental results demonstrate the superior performance of the proposed algorithm.
INFORMATION SCIENCES
(2024)
Article
Computer Science, Information Systems
Hui Tu, Shifei Ding, Xiao Xu, Haiwei Hou, Chao Li, Ling Ding
Summary: Border-Peeling algorithm is a density-based clustering algorithm, but its complexity and issues on unbalanced datasets restrict its application. This paper proposes a non-iterative border-peeling clustering algorithm, which improves the clustering performance by distinguishing and associating core points and border points.
INFORMATION SCIENCES
(2024)
Article
Computer Science, Information Systems
Long Tang, Pan Zhao, Zhigeng Pan, Xingxing Duan, Panos M. Pardalos
Summary: In this work, a two-stage denoising framework (TSDF) is proposed for zero-shot learning (ZSL) to address the issue of noisy labels. The framework includes a tailored loss function to remove suspected noisy-label instances and a ramp-style loss function to reduce the negative impact of remaining noisy labels. In addition, a dynamic screening strategy (DSS) is developed to efficiently handle the nonconvexity of the ramp-style loss.
INFORMATION SCIENCES
(2024)
Article
Computer Science, Information Systems
Raghunathan Krishankumar, Sundararajan Dhruva, Kattur S. Ravichandran, Samarjit Kar
Summary: Health 4.0 is gaining global attention for better healthcare through digital technologies. This study proposes a new decision-making framework for selecting viable blockchain service providers in the Internet of Medical Things (IoMT). The framework addresses the limitations in previous studies and demonstrates its applicability in the Indian healthcare sector. The results show the top ranking BSPs, the importance of various criteria, and the effectiveness of the developed model.
INFORMATION SCIENCES
(2024)
Article
Computer Science, Information Systems
Tao Tan, Hong Xie, Liang Feng
Summary: This paper proposes a heterogeneous update idea and designs HetUp Q-learning algorithm to enlarge the normalized gap by overestimating the Q-value corresponding to the optimal action and underestimating the Q-value corresponding to the other actions. To address the limitation, a softmax strategy is applied to estimate the optimal action, resulting in HetUpSoft Q-learning and HetUpSoft DQN. Extensive experimental results show significant improvements over SOTA baselines.
INFORMATION SCIENCES
(2024)
Article
Computer Science, Information Systems
Chao Yang, Xianzhi Wang, Lina Yao, Guodong Long, Guandong Xu
Summary: This paper proposes a dynamic transformer-based architecture called Dyformer for multivariate time series classification. Dyformer captures multi-scale features through hierarchical pooling and adaptive learning strategies, and improves model performance by introducing feature-map-wise attention mechanisms and a joint loss function.
INFORMATION SCIENCES
(2024)
Article
Computer Science, Information Systems
Xiguang Li, Baolu Feng, Yunhe Sun, Ammar Hawbani, Saeed Hammod Alsamhi, Liang Zhao
Summary: This paper proposes an enhanced scatter search strategy, using opposition-based learning, to solve the problem of automated test case generation based on path coverage (ATCG-PC). The proposed ESSENT algorithm selects the path with the lowest path entropy among the uncovered paths as the target path and generates new test cases to cover the target path by modifying the dimensions of existing test cases. Experimental results show that the ESSENT algorithm outperforms other state-of-the-art algorithms, achieving maximum path coverage with fewer test cases.
INFORMATION SCIENCES
(2024)
Article
Computer Science, Information Systems
Shirin Dabbaghi Varnosfaderani, Piotr Kasprzak, Aytaj Badirova, Ralph Krimmel, Christof Pohl, Ramin Yahyapour
Summary: Linking digital accounts belonging to the same user is crucial for security, user satisfaction, and next-generation service development. However, research on account linkage is mainly focused on social networks, and there is a lack of studies in other domains. To address this, we propose SmartSSO, a framework that automates the account linkage process by analyzing user routines and behavior during login processes. Our experiments on a large dataset show that SmartSSO achieves over 98% accuracy in hit-precision.
INFORMATION SCIENCES
(2024)
Article
Computer Science, Information Systems
Renchao Wu, Jianjun He, Xin Li, Zuguo Chen
Summary: This paper proposes a memetic algorithm with fuzzy-based population control (MA-FPC) to solve the joint order batching and picker routing problem (JOBPRP). The algorithm incorporates batch exchange crossover and a two-level local improvement procedure. Experimental results show that MA-FPC outperforms existing algorithms in terms of solution quality.
INFORMATION SCIENCES
(2024)
Article
Computer Science, Information Systems
Guoxiang Zhong, Fagui Liu, Jun Jiang, Bin Wang, C. L. Philip Chen
Summary: In this study, we propose the AMFormer framework to address the problem of mixed normal and anomaly samples in deep unsupervised time-series anomaly detection. By refining the one-class representation and introducing the masked operation mechanism and cost sensitive learning theory, our approach significantly improves anomaly detection performance.
INFORMATION SCIENCES
(2024)
Article
Computer Science, Information Systems
Jin Zhou, Kang Zhou, Gexiang Zhang, Ferrante Neri, Wangyang Shen, Weiping Jin
Summary: In this paper, the authors focus on the issue of multi-objective optimisation problems with redundant variables and indefinite objective functions (MOPRVIF) in practical problem-solving. They propose a dual data-driven method for solving this problem, which consists of eliminating redundant variables, constructing objective functions, selecting evolution operators, and using a multi-objective evolutionary algorithm. The experiments conducted on two different problem domains demonstrate the effectiveness, practicality, and scalability of the proposed method.
INFORMATION SCIENCES
(2024)
Article
Computer Science, Information Systems
Georgios Charizanos, Haydar Demirhan, Duygu Icen
Summary: This article proposes a new fuzzy logistic regression framework that addresses the problems of separation and imbalance while maintaining the interpretability of classical logistic regression. By fuzzifying binary variables and classifying subjects based on a fuzzy threshold, the framework demonstrates superior performance on imbalanced datasets.
INFORMATION SCIENCES
(2024)
