Maximally Local Connectivity on Augmented Cubes

Y-Chuang Chen, Meng-Hung Chen, Jiann-Mean Tan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

Connectivity is all important measurement for the fault tolerance in interconnection networks. It is known that the augmented cube AQ(n) is maximally connected, i.e. (2n - 1)-connected, for n >= 4. By the classical Menger's Theorem, every pair of vertices in AQ(n) is connected by 2n - 1 vertex-disjoint paths for n >= 4. A routing with parallel paths can speed up transfers of large amounts of data and increase fault tolerance. Motivated by some research works on networks with faults, we have a further result that for any faulty vertex set F subset of V(AQ(n)) and vertical bar F vertical bar <= 2n - 7 for n >= 4, each pair of non-faulty vertices, denoted by u and v, in AQ(n) - F is connected by min{deg(f)(u), deg(f)(v)} vertex-disjoint fault-free paths, where deg(f)(u) and deg(f)(v) are the degree of u and v in AQ(n) - F, respectively. Moreover, we have another result that for ally faulty vertex set F subset of V(AQ(n)) and vertical bar F vertical bar <= 4n - 9 for n >= 4, there exists a large connected component with at least 2(n) - vertical bar F vertical bar - 1 vertices in AQ(n) - F. In general, a remaining large fault-free connected component also increases fault tolerance.
Original languageEnglish
Title of host publication9th International Conference on Algorithms and Architectures for Parallel Processing
Pages120-122
Number of pages3
Volume5574
StatePublished - 2009

Keywords

  • connectivity; local connectivity; fault tolerance; vertex-disjoint path; augmented cube
  • STRONG MENGER-CONNECTIVITY; FAULTY VERTICES; TOPOLOGICAL PROPERTIES; STAR GRAPHS; HYPERCUBE; COMPONENT; NETWORKS

Fingerprint Dive into the research topics of 'Maximally Local Connectivity on Augmented Cubes'. Together they form a unique fingerprint.

  • Cite this

    Chen, Y-C., Chen, M-H., & Tan, J-M. (2009). Maximally Local Connectivity on Augmented Cubes. In 9th International Conference on Algorithms and Architectures for Parallel Processing (Vol. 5574, pp. 120-122)