An algorithm to construct independent spanning trees on parity cubes
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 61-72 |
| Journal / Publication | Theoretical Computer Science |
| Volume | 465 |
| Publication status | Published - 21 Dec 2012 |
Link(s)
Abstract
Independent spanning trees have applications in networks such as reliable communication protocols, one-to-all broadcasting, reliable broadcasting, and secure message distribution. Thus, the designs of independent spanning trees in several classes of networks have been widely investigated. However, there is a conjecture on independent spanning trees: any n-connected graph has n independent spanning trees rooted at an arbitrary vertex. This conjecture still remains open for nQn - - a variant of n-dimensional hypercube. Furthermore, we prove that all independent spanning trees rooted at an arbitrary vertex constructed by our construction method are isomorphic and the height of each tree is n+1 for any integer n
Research Area(s)
- Fault-tolerant broadcasting, Independent spanning tree, Parity cube, Secure message distribution
Citation Format(s)
An algorithm to construct independent spanning trees on parity cubes. / Wang, Yan; Fan, Jianxi; Jia, Xiaohua et al.
In: Theoretical Computer Science, Vol. 465, 21.12.2012, p. 61-72.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
