@inproceedings{c20fa18604284b0091de7bc20efa6364,

title = "Constructing independent spanning trees for hypercubes and locally twisted cubes",

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.",

keywords = "Data broadcasting, Design and analysis of algorithms, Hypercubes, Locally twisted cubes, Parallel algorithm, Vertex-disjoint spanning trees",

author = "Liu, {Yi Jiun} and Chou, {Well Y.} and Lan, {James K.} and Chiuyuan Chen",

year = "2009",

month = dec,

day = "1",

doi = "10.1109/I-SPAN.2009.97",

language = "English",

isbn = "9780769539089",

series = "I-SPAN 2009 - The 10th International Symposium on Pervasive Systems, Algorithms, and Networks",

pages = "17--22",

booktitle = "I-SPAN 2009 - The 10th International Symposium on Pervasive Systems, Algorithms, and Networks",

note = "null ; Conference date: 14-12-2009 Through 16-12-2009",

}