Name
Title | ||
|---|---|---|
Constructing independent spanning trees with height n on the n-dimensional crossed cube. |
Abstract | ||
|---|---|---|
Independent spanning trees (ISTs) on networks have applications in reliable broadcasting, reliable communication protocols, secure message distribution. Towards the ISTs on crossed cubes, although several results have been obtained, the maximum height of the ISTs on the n-dimensional crossed cube CQn is no less than n+1 for n≥3. So we have the question whether there exist multiple ISTs with height lower than n+1 on CQn. In this paper, firstly, we present the construction of n−2 ISTs rooted at node 0 on CQn, the maximum height of which is no more than n for n≥4. A parallel algorithm with the time complexity O(N) is also presented, where N=2n. Secondly, we present a binary XOR operation to transform the above n−2 ISTs into the n−2 ISTs rooted at any node that is similar to 0 on CQn. Thirdly, we revise the recursive algorithm CIST from Cheng et al. (2013) to construct n−2 ISTs rooted at any node on CQn with the maximal height n, where the time complexity is O(Nlog2N). We have also extended the efficient parallel method to locally twisted cubes. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.future.2018.02.010 | Future Generation Computer Systems |
Keywords | Field | DocType |
Crossed cube,Independent spanning trees,Height,Reliable broadcasting | Broadcasting,Combinatorics,Recursion (computer science),Bitwise operation,Parallel algorithm,Computer science,Independent spanning trees,Time complexity,Binary number,Cube,Distributed computing | Journal |
Volume | ISSN | Citations |
87 | 0167-739X | 1 |
PageRank | References | Authors |
0.35 | 25 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cheng Baolei | 1 | 10 | 5.56 |
| Jianxi Fan | 2 | 718 | 60.15 |
| Qiang Lyu | 3 | 7 | 3.16 |
| Jing-Ya Zhou | 4 | 64 | 16.35 |
| Zhao Liu | 5 | 25 | 10.73 |