Towards the Independent Spanning Trees in Conditional BC Networks

Bao Lei Cheng, Jian Xi Fan, Shu Kui Zhang, Yan Wang, Xi Wang, Wen Jun Liu2013 · DOI

Abstract

Independent spanning trees (ISTs) are fundamental to reliable and secure communication in interconnection networks. While the IST conjecture—stating that any $n$-connected graph possesses $n$ ISTs—remains an open problem for $n \geq 5$, this paper presents a significant advancement. We introduce Algorithm XIST, a generalized recursive framework designed to construct $n$ ISTs in a broad class of hypercube-like topologies termed "conditional BC networks." By leveraging structural isomorphisms and extendable node sets, our method provides a unified constructive proof for various network variants, including Möbius cubes, crossed cubes, and a new variant, the HMH cube.

Introduction

In the realm of parallel and distributed computing, the efficiency and reliability of the interconnection network are paramount. Independent Spanning Trees (ISTs) serve as a robust mechanism for fault-tolerant broadcasting and secure message distribution. A set of spanning trees is considered independent if, for any destination node, the paths from the root to that node across different trees are node-disjoint (sharing no common internal nodes or edges). This property ensures that communication can persist even in the face of multiple node or link failures.

The IST Conjecture posits that any $n$-connected graph has $n$ ISTs rooted at any arbitrary node. Despite its importance, the conjecture has only been proven for $n \leq 4$. Previous efforts to solve it for higher dimensions have often been ad-hoc, focusing on specific graph families. This research addresses the need for a more general approach applicable to the diverse family of Bijective Connection (BC) networks.

The Recursive Framework: Algorithm XIST

A Bijective Connection (BC) network $X_n$ of dimension $n$ is defined recursively: it consists of two $(n-1)$-dimensional sub-networks, $X_{n-1}^0$ and $X_{n-1}^1$, connected by a perfect matching (a bijection) between their node sets.

Figure 4: Structural representation of a 4-dimensional BC network formed by linking two 3-dimensional sub-networks.

Algorithm XIST utilizes this recursive structure through two primary rules:

  1. Rule 1 (Isomorphic Construction): This rule ensures that the ISTs constructed in the sub-networks are isomorphic in terms of their "dimension-backbone." This consistency allows the trees to be aligned and merged without conflicts in the higher-dimensional space.
  2. Rule 2 (The Merge): To combine trees from $X_{n-1}^0$ and $X_{n-1}^1$, the algorithm employs Extendable Node Sets (ENS). These sets partition the nodes such that each tree "claims" a specific set of paths, preventing overlaps and maintaining the node-disjoint requirement across the entire $n$-dimensional network.

Constructive Proof and Results

The authors define "conditional BC networks" as those where these recursive properties are mathematically guaranteed. This classification encompasses nearly all major hypercube variants studied over the last two decades, such as standard hypercubes ($Q_n$), locally twisted cubes ($LTQ_n$), and Möbius cubes ($MQ_n$).

To demonstrate the algorithm's versatility, the paper introduces the HMH Cube (Hierarchical Möbius Hypercube) and applies Algorithm XIST to construct four ISTs for $HMH_4$.

Figure 5: The recursive merging process of sub-trees to form independent spanning trees in a higher-dimensional network.

The results confirm that for any $n$-dimensional conditional BC network ($n \geq 2$), Algorithm XIST successfully constructs $n$ ISTs. This provides a constructive proof that moves the field closer to a general solution for the IST conjecture within the hypercube family.

Conclusion

Algorithm XIST represents a shift from ad-hoc topological solutions to a unified theoretical framework. By identifying the "conditional" properties required for recursive IST construction, this work simplifies the design of reliable communication protocols for complex interconnection networks. Future research will focus on determining if all BC networks satisfy these conditions and exploring the computational efficiency of the algorithm in large-scale systems.

Summary updated

Abstract

Independent spanning trees (ISTs for short) in networks have applications such as reliable communication protocols, the multi-node broadcasting, one-to-all broadcasting, reliable broadcasting, and secure message distribution. However, it is an open problem whether there are n
BibTeX
@misc{cheng2013towards,
  author = {Bao Lei Cheng and Jian Xi Fan and Shu Kui Zhang and Yan Wang and Xi Wang and Wen Jun Liu},
  title = {{Towards the Independent Spanning Trees in Conditional BC Networks}},
  year = {2013},
  doi = {10.2991/icacsei.2013.20},
}
Figure