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

Lun-Min Shih, Jiann-Mean Tan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-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 languageEnglish
Title of host publicationPROCEEDINGS OF THE 2009 SIXTH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY: NEW GENERATIONS, VOLS 1-3
PublisherIEEE
Pages564-569
Number of pages6
ISBN (Print)978-1-4244-3770-2
StatePublished - 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