Search

In this paper, we determine the wide diameters of regular hyper-stars HS(2k, k) and folded hyper-stars FHS(2k, k). We first provide a connection between the wide diameter and the maximum height of a set of particular spanning trees, called independent spanning trees (ISTs for short), of a graph. According to this relation, we analyze the heights of ISTs constructed in the previous works to establish upper bounds of the wide diameters of HS(2k, k) and FHS(2k, k). By contrast, we take the known results of fault diameters of HS(2k, k) and FHS(2k, k) as lower bounds. Consequently, we obtain the following results: (i) Dw (HS(2k, k)) = 2k + 1 for k ≥ 2, and (ii) Dw (FHS(4, 2)) = 3 and Dw (FHS(2k, k)) = k + 2 for k ≥ 3, where Dw (G) stands for the wide diameter of a graph G. The latter gives the answer of a question arisen from a previous work [(2015) Pruning longer branches of ISTs on folded hyper-stars, Comput. J., 58, 2972-2981]. In addition, we ascertain that all ISTs of HS(2k, k) and FHS(2k, k) constructed in the previous works are optimal in the sense that their heights are minimized. [ABSTRACT FROM AUTHOR]

A long-standing conjecture mentions that a k -connected graph G admits k independent spanning trees (ISTs for short) rooted at an arbitrary node of G . An n -dimensional twisted cube, denoted by T Q n , is a variation of hypercube with connectivity n and has many features superior to those of hypercube. Yang (2010) first proposed an algorithm to construct n edge-disjoint spanning trees in T Q n for any odd integer n ⩾ 3 and showed that half of them are ISTs. At a later stage, Wang et al. (2012) inferred that the above conjecture in affirmative for T Q n by providing an O ( N log N ) time algorithm to construct n ISTs, where N = 2 n is the number of nodes in T Q n . However, this algorithm is executed in a recursive fashion and thus is hard to be parallelized. In this paper, we revisit the problem of constructing ISTs in twisted cubes and present a non-recursive algorithm. Our approach can be fully parallelized to make the use of all nodes of T Q n as processors for computation in such a way that each node can determine its parent in all spanning trees directly by referring its address and tree indices in O ( log N ) time. [ABSTRACT FROM AUTHOR]

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance, bandwidth and security. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. In this paper, we give an algorithm to construct ISTs on enhanced hypercubes Qn,k , which contain folded hypercubes as a subclass. Moreover, we show that these ISTs are near optimal for heights and path lengths. Let D(Qn,k) denote the diameter of Qn,k . If n-k is odd or n-k\in \lbrace 2,n\rbrace , we show that all the heights of ISTs are equal to D(Qn,k)+1 , and thus are optimal. Otherwise, we show that each path from a node to the root in a spanning tree has length at most D(Qn,k)+2 . In particular, no more than 2.15 percent of nodes have the maximum path length. As a by-product, we improve the upper bound of wide diameter (respectively, fault diameter) of Qn,k from these path lengths. [ABSTRACT FROM PUBLISHER]

A set of k spanning trees rooted at the same vertex r in a graph G is called independent [and the trees are called independent spanning trees (ISTs)] if, for any vertex x ≠ r, the k paths from x to r, one path in each tree, are internally disjoint. The design of ISTs on graphs has applications to fault-tolerant broadcasting and secure message distribution in networks. It was conjectured that, for any k-connected graph, there exist k ISTs rooted at any vertex of the graph. The conjecture has been proved true for k-connected graphs with k ≤ 4, and remains open otherwise. In this paper, we deal with the problem of constructing ISTs on the Cartesian product of a sequence of hybrid graphs, including cycles and complete graphs. Consequently, this result generalizes a number of previous works. Moreover, the construction is shown to be optimal in the sense that the heights of ISTs are minimized. [ABSTRACT FROM AUTHOR]

Abstract: Two spanning trees of a graph are said to be independent if they are rooted at the same vertex , and for each vertex in , the two different paths from to , one path in each tree, are internally disjoint. A set of spanning trees of is independent if they are pairwise independent. The construction of multiple independent spanning trees has many applications in network communication. For instance, it is useful for fault-tolerant broadcasting and secure message distribution. A recursive circulant graph has vertices labeled from 0 to , where , , and , and two vertices are adjacent if and only if there is an integer with such that  (mod ). In this paper, we propose an algorithm to construct multiple independent spanning trees on a recursive circulant graph with , where the number of independent spanning trees matches the connectivity of . [Copyright &y& Elsevier]

Zehavi and Itai (1989) proposed the following conjecture: every k -connected graph has k independent spanning trees (ISTs for short) rooted at an arbitrary node. An n -dimensional parity cube, denoted by PQ n , is a variation of hypercubes with connectivity n and has many features superior to those of hypercubes. Recently, Wang et al. (2012) confirmed the ISTs conjecture by providing an O ( N log N ) algorithm to construct n ISTs rooted at an arbitrary node on PQ n , where N = 2 n is the number of nodes in PQ n . However, this algorithm is executed in a recursive fashion and thus is hard to be parallelized. In this paper, we present a non-recursive and fully parallelized approach to construct n ISTs rooted at an arbitrary node of PQ n in O ( log N ) time using N processors. In particular, the constructing rule of spanning trees is simple and the proof of independency is easier than ever before. [ABSTRACT FROM AUTHOR]

Abstract: Fault-tolerant broadcasting and secure message distribution are important issues for network applications. It is a common idea to design multiple spanning trees with a specific property in the underlying graph of a network to serve as a broadcasting scheme or a distribution protocol for receiving high levels of fault-tolerance and security. An -dimensional folded hypercube, denoted by , is a strengthening variation of hypercube by adding additional links between nodes that have the furthest Hamming distance. In, , Ho(1990) proposed an algorithm for constructing edge-disjoint spanning trees each with a height twice the diameter of . Yang et al. (2009), recently proved that Ho’s spanning trees are indeed independent, i.e., any two spanning trees have the same root, say , and for any other node , the two different paths from to , one path in each tree, are internally node-disjoint. In this paper, we provide another construction scheme to produce independent spanning trees of , where the height of each tree is equal to the diameter of plus one. As a result, the heights of independent spanning trees constructed in this paper are shown to be optimal. [Copyright &y& Elsevier]

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and bandwidth. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Tang et al. [S.-M. Tang, Y.-L. Wang, Y.-H. Leu, Optimal independent spanning trees on hypercubes, Journal of Information Science and Engineering 20 (2004) 143–155] studied the problem of constructing k ISTs on k-dimensional hypercube Q k , and provided a recursive algorithm for their construction (i.e., for constructing k ISTs of Q k , it needs to build k −1 ISTs of Q k−1 in advance). This kind of construction forbids the possibility that the algorithm could be parallelized. In this paper, based on a simple concept called Hamming distance Latin square, we design a new algorithm for generating k ISTs of Q k . The newly proposed algorithm relies on a simple rule and is easy to be parallelized. As a result, we show that the ISTs we constructed are optimal in the sense that both the heights and the average path length of trees are minimized. [Copyright &y& Elsevier]

• We prove that a highly scalable data center network (HSDC) is vertex-symmetric. • We investigate the independent spanning trees (IST) problem on HSDC. • We propose an algorithm to construct n ISTs on the n -dimensional HSDC, denoted as H S n. • The algorithm can be parallelized to run in O (n) time using N = 2 n processors. • As a by-product, we obtain the connectivity of H S n to be n. An emerging datacenter network (DCN) with high scalability called HSDC is a server-centric DCN that can help cloud computing in supporting many inherent cloud services. For example, a server-centric DCN can initiate routing for data transmission. This paper investigates the construction of independent spanning trees (ISTs for short), a set of the rooted spanning trees associated with the disjoint-path property, in HSDC. Regarding multiple spanning trees as routing protocol, ISTs have applications in data transmission, e.g., fault-tolerant broadcasting and secure message distribution. We first establish the vertex-symmetry of HSDC. Then, by the structure that n -dimensional HSDC is a compound graph of an n -dimensional hypercube Q n and n -clique K n , we amend the algorithm constructing ISTs for Q n to obtain the algorithm required by HSDC. Unlike most algorithms of recursively constructing tree structures, our algorithm can find every node's parent in each spanning tree directly via an easy computation relied upon only the node address and tree index. Consequently, we can implement the algorithm for constructing n ISTs in O (n N) time, where N = n 2 n is the number of vertices of n -dimensional HSDC; or parallelize the algorithm in O (n) time using N processors. Remarkably, the diameter of the constructed ISTs is about twice the diameter of Q n. [ABSTRACT FROM AUTHOR]