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, 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
Mathematics, Applied
Jiang Zhou, Changjiang Bu, Hong-Jian Lai
Summary: This paper provides bounds on the spanning tree packing number and the arboricity of graphs in terms of effective resistances, offering a calculation method. Applications demonstrate that equiarboreal graphs are uniformly dense and determine the maximum number of edge-disjoint spanning c-forests of equiarboreal graphs. Furthermore, the arboricity of a regular graph can be directly derived from the effective resistance bounds provided.
DISCRETE APPLIED MATHEMATICS
(2021)
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
Mathematics, Applied
Hongwei Qiao, Eminjan Sabir, Jixiang Meng
Summary: Embedding cycles into network topology is crucial for network simulation, especially embedding Hamiltonian cycles for well-designed interconnection networks.
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Computer Science, Information Systems
Qing Chen, Oded Lachish, Sven Helmer, Michael H. Bohlen
Summary: Answering connectivity queries is crucial for fully dynamic graphs, and existing work offers data structures and algorithms with worst case guarantees. In this paper, we propose a novel data structure called the dynamic tree (D-tree) and present algorithms for its construction and maintenance. D-tree is the first data structure that can handle fully dynamic graphs with millions of vertices and edges, providing faster connectivity query answers on average than data structures with worst case guarantees.
PROCEEDINGS OF THE VLDB ENDOWMENT
(2022)
Article
Computer Science, Information Systems
Diego Lopez-Pajares, Elisa Rojas, Juan A. Carral, Isaias Martinez-Yelmo, Joaquin Alvarez-Horcajo
Summary: The paper presents an algorithm that addresses the scalability issues in multipath communication by efficiently discovering multiple disjoint paths while maintaining bounded computational cost and ensuring scalability.
The proposed algorithm has been validated through theoretical analysis and exhaustive experimental evaluation, showing significantly higher efficiency in obtaining disjoint paths compared to competitors.
Article
Mathematics, Applied
Xiaodong Chen, Qinghai Liu, Xiwu Yang
Summary: A graph G is a split graph if its vertex set V(G) can be partitioned into a clique D and an independent set I. In this paper, we prove that a Hamiltonian split graph with |D| > max{3, |I|} contains two completely independent spanning trees (CISTs). We also show that a Hamiltonian split graph with a toughness value r(G) > 1 contains two CISTs. As a corollary, we obtain that every 32-tough split graph contains two CISTs.
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Physics, Fluids & Plasmas
C. Tyler Diggans, Erik M. Bollt, Daniel ben-Avraham
Summary: This study presents a link-by-link rule-based method for constructing a collection of spanning trees with desired properties, offering a solution for optimization problems in complex networks.
Article
Mathematics, Applied
Jinn-Shyong Yang, Xiao-Yan Li, Sheng-Lung Peng, Jou-Ming Chang
Summary: The emerging data center network HSDC is a server-centric DCN that supports various cloud services and applications through the construction of independent spanning trees. This study focuses on establishing the vertex-symmetry of HSDC and modifying the algorithm for constructing ISTs to fit the requirements of HSDC. The algorithm developed can construct n ISTs in O(nN) time or parallelize the process in O(n) time using N processors, resulting in ISTs with a diameter about twice that of Q(n).
APPLIED MATHEMATICS AND COMPUTATION
(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
Operations Research & Management Science
Dmitry B. Mokeev, Dmitry S. Malyshev
Summary: The paper discusses a class of graphs with specific path properties, called Konig graphs, for k-paths and all spanning supergraphs. For odd k, a set of minimal forbidden subgraphs is identified, and a method for constructing such graphs is proposed.
OPTIMIZATION LETTERS
(2022)
Article
Mathematics
Xiaodong Chen, Mingchu Li, Liming Xiong
Summary: This paper investigates the existence of two completely independent spanning trees in a graph and its relationship with the closure of the graph.
DISCRETE MATHEMATICS
(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
Mathematics
Toru Hasunuma
Summary: This paper investigates the maximum number of completely independent spanning trees in a line graph and provides various results and properties.
GRAPHS AND COMBINATORICS
(2023)
Article
Computer Science, Information Systems
Jing Li, Xujing Li, Eddie Cheng
Summary: The study shows that the split-star network S-n(2) is super spanning connected, where n >= 4, based on recent findings regarding the alternating group graph AG(n).
INFORMATION PROCESSING LETTERS
(2021)
Article
Computer Science, Interdisciplinary Applications
Tianlong Ma, Eddie Cheng, Yaping Mao, Xu Wang
Summary: This paper investigates the maximum fractional matching of a graph and provides some sufficient and necessary conditions to characterize it. Furthermore, it also obtains sharp lower bounds of the fractional matching number for Cartesian product, strong product, lexicographic product, and direct product.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Article
Computer Science, Hardware & Architecture
Yanze Huang, Limei Lin, Eddie Cheng, Li Xu
Summary: This paper focuses on the reliability of a multiprocessor system, with an emphasis on the component diagnosability and component connectivity of a graph. The paper proposes the r-component diagnosability of the n-dimensional alternating group graph AG(n) under the PMC model, and presents a good construction for the general r-component connectivity of AG(n) where 6 <= r <= n - 1. Theoretical analysis and simulation results show that the general r-component connectivity of AG(n) is higher than that of Q(n), D-n, and FQ(n).
Article
Computer Science, Theory & Methods
Eddie Cheng, Laszlo Liptak, Ke Qiu, Zhizhang Shen
Summary: This article discusses the importance of connectivity type measures in network analysis, particularly in analyzing vulnerability and resiliency of interconnection networks. The article studies a way to extend known results in this area by considering the structure of the resulting graph when many vertices are deleted.
JOURNAL OF INTERCONNECTION NETWORKS
(2022)
Article
Mathematics, Applied
Jinyu Zou, Yaping Mao, Zhao Wang, Eddie Cheng
Summary: This paper investigates the fractional matching preclusion number of a graph, providing sharp upper and lower bounds for this number. It also characterizes graphs with large and small fractional matching preclusion numbers. Furthermore, it explores extremal problems related to the fractional matching preclusion number.
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Computer Science, Theory & Methods
Mohamad Abdallah, Eddie Cheng
Summary: This paper focuses on a class of Cayley graphs generated by certain 3-cycles on the alternating group An as models for interconnection networks. The fault-Hamiltonian connectivity of these graphs is analyzed, and it is proven that these graphs are (2n - 7)-fault-tolerant Hamiltonian connected.
THEORETICAL COMPUTER SCIENCE
(2022)
Article
Computer Science, Theory & Methods
Eddie Cheng, Yaping Mao, Ke Qiu, Zhizhang Shen
Summary: This paper presents a general approach for deriving diagnosability results of various interconnection networks. Demonstrative examples are provided to show the effectiveness of this approach, and the g-extra diagnosabilities of the hypercube, the (n, k)-star, and the arrangement graph are derived. These results agree with previous findings and eliminate the need for duplicating independent technical details, with some results having a larger applicable range.
INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS
(2022)
Article
Computer Science, Theory & Methods
Mohamad Abdallah, Eddie Cheng
Summary: This article investigates the conditional strong matching preclusion number for the pancake graph, which is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings.
INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS
(2023)
Article
Computer Science, Theory & Methods
Sambhav Gupta, Eddie Cheng, Laszlo Liptak
Summary: This paper investigates the conditional fractional strong matching preclusion number for burnt pancake graphs and a subset of the class of pancake-like graphs.
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS- COMPUTER SYSTEMS THEORY
(2022)
Article
Mathematics, Applied
Hong Zhang, Shuming Zhou, Eddie Cheng, Sun-Yuan Hsieh
Summary: The topology of multiprocessor systems is crucial for reliability evaluation in big data analysis. By analyzing the component connectivity, the fault-tolerability of the network can be measured, and system-level diagnosis strategies can be implemented. This paper presents general characteristics of component diagnosability for regular networks and provides empirical analysis on well-known regular networks.
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Computer Science, Theory & Methods
Xiaoqing Liu, Shuming Zhou, Eddie Cheng, Hong Zhang
Summary: With the rapid development of network technology, a multiprocessor system consisting of multiple processors and communication links plays a significant role in the big data era. The topology of a multiprocessor system greatly influences network performance and the design of a high-performance network architecture is of great importance. This paper proposes a more general class of balanced hypercubes and explores their basic properties. It also demonstrates the connectivity, super connectivity, extra connectivity, and (extra) diagnosability of these hypercubes. (c) 2022 Elsevier B.V. All rights reserved.
THEORETICAL COMPUTER SCIENCE
(2023)
Article
Computer Science, Hardware & Architecture
Hong Zhang, Shuming Zhou, Eddie Cheng
Summary: In this work, a novel diagnostic strategy based on cyclic connectivity, namely the cyclic diagnosability, is proposed. The cyclic diagnosability of hypercube Q(n) under the PMC model and the MM* model is investigated, and it is shown that ct(Q(n)) = 5n -10 for n = 7.
Article
Mathematics, Applied
Hong Zhang, Shuming Zhou, Eddie Cheng
Summary: This study investigates the m-restricted (edge) connectivity of the Cayley graph En, generated by G(X) with a maximum matching number h. When 1 < m < h, it is proven that the m-restricted (edge) connectivity of En is Kappa m(En) = 2m(n - 1 - m) (resp., lambda m(En) = 2m(n - 1 - m)).
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Mathematics
Yaping Mao, Christopher Melekian, Eddie Cheng
Summary: In a connected graph G=(V, E), an S-Steiner tree is a subgraph T=(V', E') that is a tree with a vertex subset S of V(G). If each vertex of S in T has a degree of 1, it is called a pendant S-Steiner tree. Two S-Steiner trees are internally disjoint if they do not share any vertices other than S and have no common edges. The pendant tree-connectivity tau(G)(S) is the maximum number of internally disjoint pendant S-Steiner trees in G for S subset of V(G) with |S|>=2, and the k-pendant tree-connectivity tau(k)(G) is the minimum value of tau(G)(S) among all sets S with k vertices. We provide a lower bound for tau(3)(G o H), where G and H are connected graphs and o denotes the lexicographic product.
CZECHOSLOVAK MATHEMATICAL JOURNAL
(2023)
Proceedings Paper
Mathematics, Applied
Eddie Cheng, Laszlo Liptak, Daniel Tian
Summary: This paper explores the concept of Extraconnectivity and computes the g-extraconnectivity of small arrangement graphs (with g <= 6). Additionally, an asymptotic result for general g is provided.
COMBINATORICS, GRAPH THEORY AND COMPUTING, SEICCGTC 2020
(2022)
