Paired 2-disjoint path covers of multi-dimensional torus networks with 2n − 3 faulty edges

Jing Li; Guoren Wang; Lichao Chen

doi:10.1016/j.tcs.2017.03.008

Paired 2-disjoint path covers of multi-dimensional torus networks with 2n − 3 faulty edges

Jing Li
, Guoren Wang^*
, Lichao Chen

^*Corresponding author for this work

Taiyuan University of Science and Technology
Northeastern University China

Research output: Contribution to journal › Article › peer-review

18 Citations (Scopus)

Abstract

The n-dimensional torus T(k₁,k₂,…,k_n) (including the k-ary n-cube Q_n^k) is one of the most popular interconnection networks. A paired k-disjoint path cover (paired k-DPC for short) of a graph is a set of k disjoint paths joining k distinct source-sink pairs that cover all vertices of the graph. In this paper, we consider the paired 2-DPC problem of n-dimensional torus. Assuming k_i≥3 for i=1,2,…,n, with at most one k_i being even, then T(k₁,k₂,…,k_n) with at most 2n−3 faulty edges always has a paired 2-DPC. And the upper bound 2n−3 of edge faults tolerated is optimal. The result is a supplement of the results of Chen [3] and [4].

Original language	English
Pages (from-to)	1-11
Number of pages	11
Journal	Theoretical Computer Science
Volume	677
DOIs	https://doi.org/10.1016/j.tcs.2017.03.008
Publication status	Published - 16 May 2017
Externally published	Yes

Keywords

Fault-tolerant
Interconnection networks
Paired k-DPC

Access to Document

10.1016/j.tcs.2017.03.008

Cite this

@article{077f767f8c0747c198c0e3af7535e67d,

title = "Paired 2-disjoint path covers of multi-dimensional torus networks with 2n − 3 faulty edges",

abstract = "The n-dimensional torus T(k1,k2,…,kn) (including the k-ary n-cube Qnk) is one of the most popular interconnection networks. A paired k-disjoint path cover (paired k-DPC for short) of a graph is a set of k disjoint paths joining k distinct source-sink pairs that cover all vertices of the graph. In this paper, we consider the paired 2-DPC problem of n-dimensional torus. Assuming ki≥3 for i=1,2,…,n, with at most one ki being even, then T(k1,k2,…,kn) with at most 2n−3 faulty edges always has a paired 2-DPC. And the upper bound 2n−3 of edge faults tolerated is optimal. The result is a supplement of the results of Chen [3] and [4].",

keywords = "Fault-tolerant, Interconnection networks, Paired k-DPC",

author = "Jing Li and Guoren Wang and Lichao Chen",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2017",

month = may,

day = "16",

doi = "10.1016/j.tcs.2017.03.008",

language = "English",

volume = "677",

pages = "1--11",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Paired 2-disjoint path covers of multi-dimensional torus networks with 2n − 3 faulty edges

AU - Li, Jing

AU - Wang, Guoren

AU - Chen, Lichao

PY - 2017/5/16

Y1 - 2017/5/16

N2 - The n-dimensional torus T(k1,k2,…,kn) (including the k-ary n-cube Qnk) is one of the most popular interconnection networks. A paired k-disjoint path cover (paired k-DPC for short) of a graph is a set of k disjoint paths joining k distinct source-sink pairs that cover all vertices of the graph. In this paper, we consider the paired 2-DPC problem of n-dimensional torus. Assuming ki≥3 for i=1,2,…,n, with at most one ki being even, then T(k1,k2,…,kn) with at most 2n−3 faulty edges always has a paired 2-DPC. And the upper bound 2n−3 of edge faults tolerated is optimal. The result is a supplement of the results of Chen [3] and [4].

AB - The n-dimensional torus T(k1,k2,…,kn) (including the k-ary n-cube Qnk) is one of the most popular interconnection networks. A paired k-disjoint path cover (paired k-DPC for short) of a graph is a set of k disjoint paths joining k distinct source-sink pairs that cover all vertices of the graph. In this paper, we consider the paired 2-DPC problem of n-dimensional torus. Assuming ki≥3 for i=1,2,…,n, with at most one ki being even, then T(k1,k2,…,kn) with at most 2n−3 faulty edges always has a paired 2-DPC. And the upper bound 2n−3 of edge faults tolerated is optimal. The result is a supplement of the results of Chen [3] and [4].

KW - Fault-tolerant

KW - Interconnection networks

KW - Paired k-DPC

UR - https://www.scopus.com/pages/publications/85017099725

U2 - 10.1016/j.tcs.2017.03.008

DO - 10.1016/j.tcs.2017.03.008

M3 - Article

AN - SCOPUS:85017099725

SN - 0304-3975

VL - 677

SP - 1

EP - 11

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Paired 2-disjoint path covers of multi-dimensional torus networks with 2n − 3 faulty edges

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this