The Construction of Multiple Independent Spanning Trees on Burnt Pancake Networks

Yi Cheng Yang, Shih Shun Kao, Ralf Klasing, Sun Yuan Hsieh, Hsin Hung Chou, Jou Ming Chang

Research output: Contribution to journalArticlepeer-review


A set of the spanning trees in a graph G is called independent spanning trees if they have a common root r and for each vertex v\in V(G)\setminus \{r\} , the paths from v to r in any two trees are directed edge-disjoint and internally vertex-disjoint. The construction of independent spanning trees has many practical applications in reliable communication networks, such as fault-tolerant transmission and secure message distribution. A burnt pancake network BP_{n} is a kind of Cayley graph, which has been proposed as the topology of an interconnection network. In this paper, we provide a two stages construction scheme that can be used to construct a maximal number of independent spanning trees on a burnt pancake network in O(N\times n) time, where N is the number of nodes of BP_{n} and n is the dimension of the network. Furthermore, we prove the correctness of our proposed algorithm in constructing independent spanning trees.

Original languageEnglish
Article number9314008
Pages (from-to)16679-16691
Number of pages13
JournalIEEE Access
Publication statusPublished - 2021

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Materials Science(all)
  • Engineering(all)


Dive into the research topics of 'The Construction of Multiple Independent Spanning Trees on Burnt Pancake Networks'. Together they form a unique fingerprint.

Cite this