Constructing Completely Independent Spanning Trees in a Family of Line-Graph-Based Data Center Networks

Yifeng Wang, Baolei Cheng, Yu Qian, Dajin Wang

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

The past decade has seen growing importance being attached to the {\em Completely Independent Spanning Trees} (CISTs). The CISTs can facilitate many network functionalities, and the existence and construction schemes of CISTs in various networks can be an indicator of the network's robustness. In this paper, we establish the number of CISTs that can be constructed in the {\em line graph} of the complete graph <formula><tex>$K_n$</tex></formula> (denoted <formula><tex>$L(K_n)$</tex></formula>, for <formula><tex>$n\geq4$</tex></formula>), and present an algorithm to construct the optimal (i.e. maximal) number of CISTs in <formula><tex>$L(K_n)$</tex></formula>. The <formula><tex>$L(K_n)$</tex></formula> is a special class of SWCube \cite{Li001}, an architectural model proposed for data center networks. Our construction algorithm is also implemented to verify its validity.

Original languageEnglish
JournalIEEE Transactions on Computers
DOIs
StateAccepted/In press - 2021

Keywords

  • Bipartite graph
  • Color
  • Computer science
  • Data centers
  • Data models
  • Ink
  • Terminology

Fingerprint

Dive into the research topics of 'Constructing Completely Independent Spanning Trees in a Family of Line-Graph-Based Data Center Networks'. Together they form a unique fingerprint.

Cite this