Constructing dual-CISTs of DCell data center networks

Xiao-Wen Qin, Jou-Ming Chang and Rong-Xia Hao

Applied Mathematics and Computation, 2019, vol. 362, issue C, -

Abstract: The k-dimensional data center network with n port switches, denoted by Dk,n, has been proposed as a structure of the server-centric network and it was required to have a high reliability on data transmission. A set of t spanning trees in a graph G are called completely independent spanning trees (CISTs for short) if for every pair of nodes x, y ∈ V(G), the paths joining x and y in any two trees have neither node nor edge in common, except for x and y. In particular, if t=2, the two CISTs are called a dual-CIST. Although it has been proved that determining if a graph G admits t CISTs is an NP-complete problem even for t=2, the construction of multiple CISTs on the underlying graph of a network has applications in the fault-tolerance of data transmission. In this paper, we provide a recursive construction for building a dual-CIST on Dk,n for k ≥ 0 and n ≥ 6.

Keywords: Completely independent spanning trees; Data center network; Fault-tolerance (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300319305296
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:362:y:2019:i:c:50

DOI: 10.1016/j.amc.2019.06.060

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().