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
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
Zhiyong Pan, Baolei Cheng, Jianxi Fan, Yan Wang, Xiajing Li
Summary: This paper investigates the application of line graphs of conditional BC networks in data center networks. The authors propose a parallel algorithm to construct 2n - 2 edge independent spanning trees (EISTs) rooted at an arbitrary node on L(XCn), and prove the correctness of the algorithm. Finally, a simulation result of the algorithm is provided.
THEORETICAL COMPUTER SCIENCE
(2023)
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
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
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
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
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
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
Computer Science, Hardware & Architecture
Jiale Huang, Lulu Zheng, Yalan Wu, Peng Liu, Jigang Wu
Summary: This study aims to quickly restore the faulty survivable spanning connection (SSC) by adjusting and updating the faulty spanning trees. Two fast restoration algorithms are proposed and simulation results show that they can significantly reduce the recovery time and achieve nearly optimal network survivability.
COMPUTERS & ELECTRICAL ENGINEERING
(2022)
Article
Operations Research & Management Science
Pedro Correia, Luis Paquete, Jose Rui Figueira
Summary: This article introduces a new algorithm based on the connectedness property for computing the set of supported non-dominated points and corresponding efficient solutions for the multi-objective spanning tree problem. The algorithm utilizes decomposition of the weight set and adjacency relation in the decision space to determine efficient spanning trees and indifference regions. An in-depth computational analysis is presented for different types of networks with three objectives.
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
(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
Amarja Kathapurkar, Richard Montgomery
Summary: The study proves that for every given alpha value, there exists an appropriate c value and n(0) such that when the size of the graph is greater than or equal to n(0), the directed graph with a minimum semi-degree of at least (1/2 + alpha)n contains a copy of every oriented tree with a maximum degree of at most cn/log n. This result improves previous research and does not use specific regularity lemma.
JOURNAL OF COMBINATORIAL THEORY SERIES B
(2022)
Article
Computer Science, Hardware & Architecture
Xi Wang, Alejandro Erickson, Jianxi Fan, Xiaohua Jia
Article
Computer Science, Hardware & Architecture
Yanan Chang, Xiaohua Jia, Jianqun Cui
COMPUTERS & ELECTRICAL ENGINEERING
(2015)
Article
Computer Science, Theory & Methods
Ruitao Xie, Yonggang Wen, Xiaohua Jia, Haiyong Xie
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2015)
Article
Computer Science, Theory & Methods
Kan Yang, Xiaohua Jia, Kui Ren
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2015)
Article
Computer Science, Interdisciplinary Applications
Marjan Marzban, Qian-Ping Gu, Xiaohua Jia
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2016)
Article
Computer Science, Information Systems
Xu Xu, Weifa Liang, Xiaohua Jia, Wenzheng Xu
WIRELESS COMMUNICATIONS & MOBILE COMPUTING
(2016)
Article
Telecommunications
Kunxiao Zhou, Liming Xie, Xiaohua Jia
WIRELESS PERSONAL COMMUNICATIONS
(2016)
Article
Computer Science, Information Systems
Weifa Liang, Wenzheng Xu, Xiaojiang Ren, Xiaohua Jia, Xiaola Lin
ACM TRANSACTIONS ON SENSOR NETWORKS
(2016)
Article
Computer Science, Information Systems
Kan Yang, Zhen Liu, Xiaohua Jia, Xuemin Sherman Shen
IEEE TRANSACTIONS ON MULTIMEDIA
(2016)
Article
Computer Science, Hardware & Architecture
Zhao Liu, Jianxi Fan, Xiaohua Jia
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
(2016)
Article
Computer Science, Information Systems
Kuai Xu, Feng Wang, Xiaohua Jia
SECURITY AND COMMUNICATION NETWORKS
(2016)
Article
Computer Science, Theory & Methods
Xi Wang, Jianxi Fan, Xiaohua Jia, Cheng-Kuan Lin
THEORETICAL COMPUTER SCIENCE
(2016)
Proceedings Paper
Computer Science, Interdisciplinary Applications
Hongwei Du, Rongrong Zhu, Xiaohua Jia, Chuang Liu
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, (COCOA 2015)
(2015)
Proceedings Paper
Computer Science, Theory & Methods
Peng-Jun Wan, Fahad Al-Dhelaan, Xiaohua Jia, Baowei Wang, Guowen Xing
2015 IEEE CONFERENCE ON COMPUTER COMMUNICATIONS (INFOCOM)
(2015)