Article
Mathematics, Applied
Meijie Ma, Chaoming Guo, Xiang-Jun Li
Summary: The paper discusses the problem of embedding internally disjoint paths in an enhanced hypercube and proves that the subgraph obtained by deleting the faulty subnetwork from the enhanced hypercube remains strong Menger connected even when the network has faults.
JOURNAL OF APPLIED MATHEMATICS AND COMPUTING
(2023)
Article
Computer Science, Information Systems
Weibei Fan, Jianxi Fan, Zhijie Han, Peng Li, Yujie Zhang, Ruchuan Wang
Summary: This paper mainly studies the fault tolerant Hamiltonian properties of a faulty locally exchanged twisted cube, LeTQ(s, t) - (f(v) + f(e)), proving that for s > 2, t > 3, and s <= t, an LeTQ(s, t) can tolerate up to s - 1 faulty vertices and edges when embedding a Hamiltonian cycle. Furthermore, it is also proven that there is a Hamiltonian path between any two distinct fault-free vertices in a faulty LeTQ(s, t) with up to (s - 2) faulty vertices and edges. The results demonstrate that LeTQ(s, t) is (s - 1)-Hamiltonian and (s - 2)-Hamiltonian-connected, achieving optimal (s - 1)-fault-tolerant Hamiltonicity and (s - 2) fault-tolerant Hamiltonian connectivity.
FRONTIERS OF COMPUTER SCIENCE
(2021)
Article
Computer Science, Theory & Methods
Cheng-Nan Lai
Summary: The study in this paper focuses on constructing m node-disjoint paths in a folded hypercube to minimize the total length and maximal length, where m <= n+1. By utilizing two specific routing functions, the construction of these paths can be efficiently carried out for odd and even routing, providing strong evidence for the effective applications of routing functions in deriving node-disjoint paths.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2021)
Article
Mathematics, Applied
Pranava K. Jha
Summary: An exchanged hypercube is a spanning subgraph of a hypercube that retains desirable properties while reducing interconnection complexity. This paper proves that the graph is isomorphic to an induced subgraph of the hypercube of minimum size, with the minimal hypercube comprising two factors, each containing vertex-disjoint copies of the induced subgraph. The result also applies to the dual-cube, a special case of the exchanged hypercube.
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Computer Science, Theory & Methods
Baohua Niu, Shuming Zhou, Tao Tian, Qifan Zhang
Summary: This paper investigates the wide diameter and fault diameter of the exchanged crossed cube (ECQ), and evaluates its performance and reliability by constructing internally vertex disjoint paths. The upper and lower bounds of these diameters are determined, demonstrating that ECQ is more efficient and reliable than the exchanged hypercube.
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
(2023)
Article
Mathematics, Applied
Ruichao Niu, Min Xu, Hong-Jian Lai
Summary: The text discusses the study of specific bipancyclic properties in bipartite graphs, focusing on generalized hypercubes and k-ary n-cubes. It examines the 2-DCC vertex bipancyclicity and identifies exceptional graphs, showing that certain criteria must be met for a n-dimensional bipartite generalized hypercube to be considered 2-DCC vertex [4, |V(G)|/2]-bipancyclic. Additionally, it demonstrates the vertex-bipancyclicity and 2-DCC bipancyclicity properties in n-dimensional bipartite generalized hypercubes and extends these properties to n-dimensional bipartite k-ary n-cubes.
APPLIED MATHEMATICS AND COMPUTATION
(2021)
Article
Computer Science, Information Systems
Janusz Dybizbanski, Andrzej Szepietowski
Summary: This paper investigates hypercubes with pairwise disjoint faulty edges and proves that all other hypercubes are Hamiltonian when n >= 4, as long as there are two healthy crossing edges of different parity in each dimension.
INFORMATION PROCESSING LETTERS
(2021)
Article
Computer Science, Information Systems
Keiichi Kaneko, Antoine Bossard, Frederick C. Harris
Summary: This paper discusses the importance of the bijective connection graph and the set-to-set disjoint paths problem. It proposes an algorithm with polynomial-order time complexity for constructing disjoint paths between any pair of node sets in n-dimensional bijective connection graphs.
Article
Computer Science, Hardware & Architecture
Xi Wang, Jianxi Fan, Shukui Zhang, Jia Yu
Summary: This paper explores the construction of node-to-set disjoint paths in an n-dimensional cross-cube C-n, presenting an O(Nlog(2)N) algorithm and simulation results for the maximal length of disjoint paths obtained by the algorithm.
JOURNAL OF SUPERCOMPUTING
(2022)
Article
Computer Science, Theory & Methods
Hongxi Liu, Mingzu Zhang, Xiaowei Xu
Summary: One of the most important issues in interconnection networks is finding edge-disjoint paths that transmit information, and this paper offers a unified method to determine the minimum cardinalities of faulty links in a specific interconnection network topology. The minimum cardinalities of faulty links in this topology share the same value under different link-faulty assumptions, except for a specific case. The findings provide refined measurements for the reliability and fault-tolerance of interconnection networks.
THEORETICAL COMPUTER SCIENCE
(2023)
Article
Mathematics, Applied
Dongqin Cheng
Summary: The alternating group graph has been extensively studied in recent years due to its many desirable properties. This paper proves that the n-dimensional alternating group graph is panyclic with a specific disjoint-cycle-cover property for n >= 4.
APPLIED MATHEMATICS AND COMPUTATION
(2022)
Article
Computer Science, Theory & Methods
Huazhong Lu, Tingzeng Wu
Summary: This paper discusses the many-to-many k-disjoint path cover of a graph G and the balanced hypercube BHn, proving the existence of an unpaired many-to-many (2n-2)-disjoint path cover in BHn, while also improving existing results. The upper bound of 2n-2 is proven to be the best possible in terms of the number of disjoint paths in unpaired many-to-many k-DPC of BHn.
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
(2021)
Article
Computer Science, Information Systems
Guowei Dai, Longkun Guo, Gregory Gutin, Xiaoyan Zhang, Zan-Bo Zhang
Summary: This paper investigates the performance of the min-sum belief propagation (BP) algorithm for the vertex-disjoint shortest k-path problem (k-VDSP) on weighted directed graphs. The paper derives iterative message-passing update rules and proves that the BP algorithm converges to the unique optimal solution in a certain number of iterations. This is the first instance where the BP algorithm is proven to be correct for NP-hard problems.
IEEE TRANSACTIONS ON INFORMATION THEORY
(2022)
Article
Computer Science, Theory & Methods
Chao Wei, Rong-Xia Hao, Jou-Ming Chang
Summary: This paper focuses on constructing internally disjoint S-trees with |S| = 3 in the n-dimensional augmented cube A Q(n), and completely determines the kappa(3)-connectivity of A Q(n).
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2021)
Article
Computer Science, Theory & Methods
Yuxing Yang, Ningning Song
Summary: This article introduces the n-dimensional balanced hypercube BHn as a candidate interconnection network for multiprocessor systems, and proves that under certain conditions, BHn can achieve fault-free Hamiltonian paths between nodes.
THEORETICAL COMPUTER SCIENCE
(2023)
