On strong menger-connectivity of star graphs Conference Paper uri icon

abstract

  • Springer-Verlag Berlin Heidelberg 2001. Motivated by parallel routing in networks with faults, we study the following graph theoretical problem. Let G be a d-regular graph. We say that G is strongly enger-connected if for any copy Gf of G with at most d - 2 nodes removed, every pair of nodes u and v in Gf are connected by min{degf(u), degf(v)} node-disjoint paths in Gf, where degf(u) and degf(v) are the degrees of the nodes u and v in Gf, respectively. We show that the star graphs, which are a recently proposed attractive alternative to the widely used hypercubes as network models, are strongly Menger-connected. An algorithm of optimal running time is developed that constructs the maximum number of node-disjoint paths of nearly optimal length in star graphs with faults.

name of conference

  • Graph-Theoretic Concepts in Computer Science, 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14-16, 2001, Proceedings

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Oh, E., & Chen, J.

complete list of authors

  • Oh, E||Chen, J

publication date

  • January 2001