Name
Title | ||
|---|---|---|
Dimensional-permutation-based independent spanning trees in bijective connection networks |
Abstract | ||
|---|---|---|
In recent years, there are many new findings on independent spanning trees (ISTs for short) in hypercubes, crossed cubes, locally twisted cubes, and Möbius cubes, which all belong to a more general network category called bijective connection networks (BC networks). However, little progress has been made for ISTs in general BC networks. In this paper, we first propose the definitions of conditional BC networks and V-dimensional-permutation. We then give a linear parallel algorithm of ISTs rooted at an arbitrary vertex in conditional BC networks, which include hypercubes, crossed cubes, locally twisted cubes, and Möbius cubes, based on the ascending circular dimensional-permutation, where the ISTs are all isomorphic to the binomial-like tree. In addition, we show that there exists an efficient algorithm to construct a spanning tree rooted at an arbitrary vertex in any BC network Xn , and all V-dimensional-permutations can be used to construct spanning trees isomorphic to the n-level binomial tree and rooted at an arbitrary vertex in Xn. © 2014 IEEE. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/TPDS.2014.2307871 | IEEE Transactions on Parallel and Distributed Systems |
Keywords | Field | DocType |
Bijective connection network,binomial tree,dimensional-permutation,independent spanning trees,reliable broadcasting | Combinatorics,Bijection,Vertex (geometry),Computer science,Parallel algorithm,Permutation,Isomorphism,Spanning tree,Hypercube,Cube,Distributed computing | Journal |
Volume | Issue | ISSN |
26 | 1 | 10459219 |
Citations | PageRank | References |
8 | 0.43 | 31 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cheng Baolei | 1 | 84 | 2.81 |
| Fan Jianxi | 2 | 369 | 13.12 |
| Xiaohua Jia | 3 | 4609 | 303.30 |