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

Yifeng Wang; Baolei Cheng; Yu Qian; Dajin Wang

doi:10.1109/TC.2021.3077587

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

Yifeng Wang, Baolei Cheng, Yu Qian, Dajin Wang

Computer Science

Research output: Contribution to journal › Article › peer-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 language	English
Journal	IEEE Transactions on Computers
DOIs	https://doi.org/10.1109/TC.2021.3077587
State	Accepted/In press - 2021

Keywords

Bipartite graph
Color
Computer science
Data centers
Data models
Ink
Terminology

Access to Document

10.1109/TC.2021.3077587

Cite this

@article{4f2a22ace4714b3ab0fa2015c8cb1428,

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

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 $K_n$ (denoted $L(K_n)$, for $n\geq4$), and present an algorithm to construct the optimal (i.e. maximal) number of CISTs in $L(K_n)$. The $L(K_n)$ 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.",

keywords = "Bipartite graph, Color, Computer science, Data centers, Data models, Ink, Terminology",

author = "Yifeng Wang and Baolei Cheng and Yu Qian and Dajin Wang",

note = "Publisher Copyright: IEEE",

year = "2021",

doi = "10.1109/TC.2021.3077587",

language = "English",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

}

TY - JOUR

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

AU - Wang, Yifeng

AU - Cheng, Baolei

AU - Qian, Yu

AU - Wang, Dajin

N1 - Publisher Copyright: IEEE

PY - 2021

Y1 - 2021

N2 - 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 $K_n$ (denoted $L(K_n)$, for $n\geq4$), and present an algorithm to construct the optimal (i.e. maximal) number of CISTs in $L(K_n)$. The $L(K_n)$ 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.

AB - 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 $K_n$ (denoted $L(K_n)$, for $n\geq4$), and present an algorithm to construct the optimal (i.e. maximal) number of CISTs in $L(K_n)$. The $L(K_n)$ 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.

KW - Bipartite graph

KW - Color

KW - Computer science

KW - Data centers

KW - Data models

KW - Ink

KW - Terminology

UR - http://www.scopus.com/inward/record.url?scp=85105586717&partnerID=8YFLogxK

U2 - 10.1109/TC.2021.3077587

DO - 10.1109/TC.2021.3077587

M3 - Article

AN - SCOPUS:85105586717

SN - 0018-9340

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this