Fault-tolerant Maximal Local-Connectivity on the Bubble-sort Graphs

Lun-Min Shih; Jiann-Mean Tan

Fault-tolerant Maximal Local-Connectivity on the Bubble-sort Graphs

Lun-Min Shih, Jiann-Mean Tan

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

Abstract

An interconnection network is usually modeled as a graph, in which vertices and edges correspond to processor and communication links, respectively. The local connectivity of two vertices is defined as the maximum number of internally vertex-disjoint paths between them. In this paper, we define two vertices to be maximally local-connected, if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. Moreover, we introduce the one-to-many version of connectivity. We show that an n-dimensional Bubble-sort Graph is maximally local-connected, even if there are at most n-3 faulty vertices in it, and prove that it is also (n-1)-fault-tolerant one-to-many maximally local-connected.

Original language	English
Title of host publication	PROCEEDINGS OF THE 2009 SIXTH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY: NEW GENERATIONS, VOLS 1-3
Publisher	IEEE
Pages	564-569
Number of pages	6
ISBN (Print)	978-1-4244-3770-2
State	Published - 27 Apr 2009

Keywords

interconnection networks
Bubble-sort graph
Connectivity
Fault-tolerant
Local connectivity

Fingerprint Dive into the research topics of 'Fault-tolerant Maximal Local-Connectivity on the Bubble-sort Graphs'. Together they form a unique fingerprint.

Cite this

@inproceedings{6273b176aa4341d982469f86fe55cd3b,

title = "Fault-tolerant Maximal Local-Connectivity on the Bubble-sort Graphs",

abstract = "An interconnection network is usually modeled as a graph, in which vertices and edges correspond to processor and communication links, respectively. The local connectivity of two vertices is defined as the maximum number of internally vertex-disjoint paths between them. In this paper, we define two vertices to be maximally local-connected, if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. Moreover, we introduce the one-to-many version of connectivity. We show that an n-dimensional Bubble-sort Graph is maximally local-connected, even if there are at most n-3 faulty vertices in it, and prove that it is also (n-1)-fault-tolerant one-to-many maximally local-connected.",

keywords = "interconnection networks, Bubble-sort graph, Connectivity, Fault-tolerant, Local connectivity",

author = "Lun-Min Shih and Jiann-Mean Tan",

year = "2009",

month = apr,

day = "27",

language = "English",

isbn = "978-1-4244-3770-2",

pages = "564--569",

booktitle = "PROCEEDINGS OF THE 2009 SIXTH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY: NEW GENERATIONS, VOLS 1-3",

publisher = "IEEE",

}

TY - GEN

T1 - Fault-tolerant Maximal Local-Connectivity on the Bubble-sort Graphs

AU - Shih, Lun-Min

AU - Tan, Jiann-Mean

PY - 2009/4/27

Y1 - 2009/4/27

N2 - An interconnection network is usually modeled as a graph, in which vertices and edges correspond to processor and communication links, respectively. The local connectivity of two vertices is defined as the maximum number of internally vertex-disjoint paths between them. In this paper, we define two vertices to be maximally local-connected, if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. Moreover, we introduce the one-to-many version of connectivity. We show that an n-dimensional Bubble-sort Graph is maximally local-connected, even if there are at most n-3 faulty vertices in it, and prove that it is also (n-1)-fault-tolerant one-to-many maximally local-connected.

AB - An interconnection network is usually modeled as a graph, in which vertices and edges correspond to processor and communication links, respectively. The local connectivity of two vertices is defined as the maximum number of internally vertex-disjoint paths between them. In this paper, we define two vertices to be maximally local-connected, if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. Moreover, we introduce the one-to-many version of connectivity. We show that an n-dimensional Bubble-sort Graph is maximally local-connected, even if there are at most n-3 faulty vertices in it, and prove that it is also (n-1)-fault-tolerant one-to-many maximally local-connected.

KW - interconnection networks

KW - Bubble-sort graph

KW - Connectivity

KW - Fault-tolerant

KW - Local connectivity

M3 - Conference contribution

SN - 978-1-4244-3770-2

SP - 564

EP - 569

BT - PROCEEDINGS OF THE 2009 SIXTH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY: NEW GENERATIONS, VOLS 1-3

PB - IEEE

ER -