Constructing completely independent spanning trees in crossed cubes

Baolei Cheng, Dajin Wang, Jianxi Fan

Research output: Contribution to journalArticlepeer-review

49 Scopus citations


The Completely Independent Spanning Trees (CISTs) are a very useful construct in a computer network. It can find applications in many important network functions, especially in reliable broadcasting, i.e., guaranteeing broadcasting operation in the presence of faulty nodes. The question for the existence of two CISTs in an arbitrary network is an NP-hard problem. Therefore most research on CISTs to date has been concerning networks of specific structures. In this paper, we propose an algorithm to construct two CISTs in the crossed cube, a prominent, widely studied variant of the well-known hypercube. The construction algorithm will be presented, and its correctness proved. Based on that, the existence of two CISTs in a special Bijective Connection network based on crossed cube is also discussed.

Original languageEnglish
Pages (from-to)100-109
Number of pages10
JournalDiscrete Applied Mathematics
StatePublished - 11 Mar 2017


  • Completely independent spanning tree
  • Crossed cube
  • Fault tolerance
  • Reliable broadcasting


Dive into the research topics of 'Constructing completely independent spanning trees in crossed cubes'. Together they form a unique fingerprint.

Cite this