Constructive algorithm of independent spanning trees on möbius cubes

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

27 Scopus Citations
View graph of relations

Author(s)

  • Baolei Cheng
  • Jianxi Fan
  • Xiaohua Jia
  • Shukui Zhang
  • Bangrui Chen

Detail(s)

Original languageEnglish
Pages (from-to)1347-1362
Journal / PublicationComputer Journal
Volume56
Issue number11
Publication statusPublished - Nov 2013
Externally publishedYes

Abstract

Independent spanning trees (ISTs) on networks have applications in networks such as reliable communication protocols, the multi-node broadcasting, one-to-all broadcasting, reliable broadcasting and secure message distribution. However, there is a problem on ISTs on graphs: If a graph G is n-connected (n >= 1), then there are n ISTs rooted at an arbitrary vertex on G. This problem has remained open for n >= 5. In this paper, we consider the construction of ISTs on Mobius cubes-a class of hypercube variants. An O(N log N) recursive algorithm is proposed to construct n ISTs rooted at an arbitrary vertex on the n-dimensional Mobius cube M-n, where N=2(n) is the number of vertices in M-n. Furthermore, we prove that each IST obtained by our algorithm is isomorphic to an n-level binomial-like tree with the height n+1 for n >= 2.

Research Area(s)

  • Binomial-like tree, Independent spanning tree, Internally vertex-disjoint path, Möbius cube

Citation Format(s)

Constructive algorithm of independent spanning trees on möbius cubes. / Cheng, Baolei; Fan, Jianxi; Jia, Xiaohua; Zhang, Shukui; Chen, Bangrui.

In: Computer Journal, Vol. 56, No. 11, 11.2013, p. 1347-1362.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review