Strong Menger connectivity with conditional faults on the class of hypercube-like networks

Lun-Min Shih; Chieh-Feng Chiang; Lih Hsing Hsu; Jiann-Mean Tan

doi:10.1016/j.ipl.2007.10.009

Strong Menger connectivity with conditional faults on the class of hypercube-like networks

Lun-Min Shih, Chieh-Feng Chiang, Lih Hsing Hsu, Jiann-Mean Tan

Department of Computer Science

Research output: Contribution to journal › Article

26 Scopus citations

Abstract

In this paper, we study the Menger property on a class of hypercube-like networks. We show that in all n-dimensional hypercubelike networks with n - 2 vertices removed, every pair of unremoved vertices u and v are connected by min{deg(u), deg(v)} vertex-disjoint paths, where deg(u) and deg(v) are the remaining degree of vertices u and v, respectively. Furthermore, under the restricted condition that each vertex has at least two fault-free adjacent vertices, all hypercube-like networks still have the strong Menger property, even if there are up to 2n - 5 vertex faults. (C) 2007 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	64-69
Number of pages	6
Journal	Information Processing Letters
Volume	106
Issue number	2
DOIs	https://doi.org/10.1016/j.ipl.2007.10.009
State	Published - 15 Apr 2008

Keywords

strong Menger connectivity; conditional faults; hypercube-like network; interconnection networks

Access to Document

10.1016/j.ipl.2007.10.009

Fingerprint Dive into the research topics of 'Strong Menger connectivity with conditional faults on the class of hypercube-like networks'. Together they form a unique fingerprint.

Cite this

@article{bfcf73ae9c594d31b40aff4866ec7428,

title = "Strong Menger connectivity with conditional faults on the class of hypercube-like networks",

abstract = "In this paper, we study the Menger property on a class of hypercube-like networks. We show that in all n-dimensional hypercubelike networks with n - 2 vertices removed, every pair of unremoved vertices u and v are connected by min{deg(u), deg(v)} vertex-disjoint paths, where deg(u) and deg(v) are the remaining degree of vertices u and v, respectively. Furthermore, under the restricted condition that each vertex has at least two fault-free adjacent vertices, all hypercube-like networks still have the strong Menger property, even if there are up to 2n - 5 vertex faults. (C) 2007 Elsevier B.V. All rights reserved.",

keywords = "strong Menger connectivity; conditional faults; hypercube-like network; interconnection networks",

author = "Lun-Min Shih and Chieh-Feng Chiang and Hsu, {Lih Hsing} and Jiann-Mean Tan",

year = "2008",

month = apr,

day = "15",

doi = "10.1016/j.ipl.2007.10.009",

language = "English",

volume = "106",

pages = "64--69",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Strong Menger connectivity with conditional faults on the class of hypercube-like networks

AU - Shih, Lun-Min

AU - Chiang, Chieh-Feng

AU - Hsu, Lih Hsing

AU - Tan, Jiann-Mean

PY - 2008/4/15

Y1 - 2008/4/15

N2 - In this paper, we study the Menger property on a class of hypercube-like networks. We show that in all n-dimensional hypercubelike networks with n - 2 vertices removed, every pair of unremoved vertices u and v are connected by min{deg(u), deg(v)} vertex-disjoint paths, where deg(u) and deg(v) are the remaining degree of vertices u and v, respectively. Furthermore, under the restricted condition that each vertex has at least two fault-free adjacent vertices, all hypercube-like networks still have the strong Menger property, even if there are up to 2n - 5 vertex faults. (C) 2007 Elsevier B.V. All rights reserved.

AB - In this paper, we study the Menger property on a class of hypercube-like networks. We show that in all n-dimensional hypercubelike networks with n - 2 vertices removed, every pair of unremoved vertices u and v are connected by min{deg(u), deg(v)} vertex-disjoint paths, where deg(u) and deg(v) are the remaining degree of vertices u and v, respectively. Furthermore, under the restricted condition that each vertex has at least two fault-free adjacent vertices, all hypercube-like networks still have the strong Menger property, even if there are up to 2n - 5 vertex faults. (C) 2007 Elsevier B.V. All rights reserved.

KW - strong Menger connectivity; conditional faults; hypercube-like network; interconnection networks

U2 - 10.1016/j.ipl.2007.10.009

DO - 10.1016/j.ipl.2007.10.009

M3 - Article

VL - 106

SP - 64

EP - 69

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 2

ER -