On strong menger-connectivity of star graphs
Conference Paper
Overview
Identity
Additional Document Info
View All
Overview
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