Constructing completely independent spanning trees in crossed cubes

Baolei Cheng, Dajin Wang, Jianxi Fan

Research output: Contribution to journalArticleResearchpeer-review

12 Citations (Scopus)

Abstract

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
Volume219
DOIs
StatePublished - 11 Mar 2017

Fingerprint

Crossed Cube
Broadcasting
Spanning tree
Computer networks
Computational complexity
Bijective
Computer Networks
NP-hard Problems
Hypercube
Correctness
Arbitrary
Vertex of a graph

Keywords

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

Cite this

@article{eb0930b04fb141abac8a62aaeb07cfe3,
title = "Constructing completely independent spanning trees in crossed cubes",
abstract = "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.",
keywords = "Completely independent spanning tree, Crossed cube, Fault tolerance, Reliable broadcasting",
author = "Baolei Cheng and Dajin Wang and Jianxi Fan",
year = "2017",
month = "3",
day = "11",
doi = "10.1016/j.dam.2016.11.019",
language = "English",
volume = "219",
pages = "100--109",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

Constructing completely independent spanning trees in crossed cubes. / Cheng, Baolei; Wang, Dajin; Fan, Jianxi.

In: Discrete Applied Mathematics, Vol. 219, 11.03.2017, p. 100-109.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Constructing completely independent spanning trees in crossed cubes

AU - Cheng, Baolei

AU - Wang, Dajin

AU - Fan, Jianxi

PY - 2017/3/11

Y1 - 2017/3/11

N2 - 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.

AB - 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.

KW - Completely independent spanning tree

KW - Crossed cube

KW - Fault tolerance

KW - Reliable broadcasting

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

U2 - 10.1016/j.dam.2016.11.019

DO - 10.1016/j.dam.2016.11.019

M3 - Article

VL - 219

SP - 100

EP - 109

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -