Construction independent spanning trees on locally twisted cubes in parallel

Yu Huei Chang, Jinn Shyong Yang, Sun Yuan Hsieh, Jou Ming Chang, Yue Li Wang

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


Let LTQn be the n-dimensional locally twisted cube. Hsieh and Tu (Theor Comput Sci 410(8–10):926–932, 2009) proposed an algorithm to construct n edge-disjoint spanning trees rooted at a particular vertex 0 in LTQn. Later on, Lin et al. (Inf Process Lett 110(10):414–419, 2010) proved that Hsieh and Tu’s spanning trees are indeed independent spanning trees (ISTs for short), i.e., all spanning trees are rooted at the same vertex r and for any other vertex v(≠ r) , the paths from v to r in any two trees are internally vertex-disjoint. Shortly afterwards, Liu et al. (Theor Comput Sci 412(22):2237–2252, 2011) pointed out that LTQn fails to be vertex-transitive for n⩾ 4 and proposed an algorithm for constructing n ISTs rooted at an arbitrary vertex in LTQn. Although this algorithm can simultaneously construct n ISTs, it is hard to be parallelized for the construction of each spanning tree. In this paper, from a modification of Hsieh and Tu’s algorithm, we present a fully parallelized scheme to construct n ISTs rooted at an arbitrary vertex in LTQn in O(n) time using 2 n vertices of LTQn as processors.

Original languageEnglish
Pages (from-to)956-967
Number of pages12
JournalJournal of Combinatorial Optimization
Issue number3
Publication statusPublished - 2017 Apr 1

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Construction independent spanning trees on locally twisted cubes in parallel'. Together they form a unique fingerprint.

Cite this