|
Multiple independent spanning trees (ISTs) can be used in broadcasting schemes and distribution protocals to provide high levels of fault-tolerance and security, respectively. Some results have been found on Qn,LTQn,TQn, etc, but so far no work has been reported on 0-Mn . In this paper, we study the exitence and construction of ISTs on Möbius cubes. We give a proof of the existence of ISTs rooted at vertex 0 on the n-dimentional Möbius cube 0-Mn and propose an O(NlogN) recursive algorithm, where n≥2 and N=2n is the number of vertices in 0-Mn. |
|
Keywords:Möbius cubes; Independent spanning tree; Internally vertex-disjoint path; Fault-tolerant broadcasting |
|