Constructing independent spanning trees for hypercubes and locally twisted cubes

Yi Jiun Liu, Well Y. Chou, James K. Lan, Chiuyuan Chen*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations

Abstract

Multiple independent spanning trees (ISTs) have applications to fault-tolerant and data broadcasting in interconnections. Thus the designs of multiple ISTs in several classes of networks have been widely investigated. There are two versions of the n ISTs conjecture. The vertex (edge) conjecture is that any n-connected (n-edge-connected) graph has n vertex-ISTs (edge-ISTs) rooted at an arbitrary vertex r. Note that the vertex conjecture implies the edge conjecture. Recently, Hsieh and Tu proposed an algorithm to construct n edge-ISTs rooted at vertex 0 for the n-dimensional locally twisted cube (LTQn), which is a variant of the n-dimensional hypercube (Q n). Since LTQn is not vertex-transitive, Hsieh and Tu's result does not solve the edge conjecture for LTQn. In the paper, we confirm the vertex conjecture (and hence also the edge conjecture) for LTQ n by proposing an algorithm to construct n vertex-ISTs rooted at any vertex. We also confirm the vertex (and also the edge) conjecture for Q n. To the best of our knowledge, our algorithm is the first algorithm that can construct n vertex-ISTs rooted at any vertex for both LTQn and Qn.

Original languageEnglish
Title of host publicationI-SPAN 2009 - The 10th International Symposium on Pervasive Systems, Algorithms, and Networks
Pages17-22
Number of pages6
DOIs
StatePublished - 1 Dec 2009
Event10th International Symposium on Pervasive Systems, Algorithms, and Networks, I-SPAN 2009 - Kaohsiung, Taiwan
Duration: 14 Dec 200916 Dec 2009

Publication series

NameI-SPAN 2009 - The 10th International Symposium on Pervasive Systems, Algorithms, and Networks

Conference

Conference10th International Symposium on Pervasive Systems, Algorithms, and Networks, I-SPAN 2009
CountryTaiwan
CityKaohsiung
Period14/12/0916/12/09

Keywords

  • Data broadcasting
  • Design and analysis of algorithms
  • Hypercubes
  • Locally twisted cubes
  • Parallel algorithm
  • Vertex-disjoint spanning trees

Fingerprint Dive into the research topics of 'Constructing independent spanning trees for hypercubes and locally twisted cubes'. Together they form a unique fingerprint.

Cite this