On strong Menger-connectivity of star graphs

被引:44
作者
Oh, E [1 ]
Chen, FE [1 ]
机构
[1] Texas A&M Univ, Dept Comp Sci, College Stn, TX 77843 USA
关键词
graph connectivity; node-disjoint paths; interconnection network;
D O I
10.1016/S0166-218X(02)00600-5
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Motivated by parallel routing in networks with faults, we study the following graph theoretical problem. Let G be a graph of minimum vertex degree d. We say that G is strongly Menger-connected if for any copy G(f) of G with at most d - 2 nodes removed, every pair of nodes u and v in G(f) are connected by min{deg(f)(u),deg(f)(v)} node-disjoint paths in G(f), where deg(f)(u) and deg(f)(v) are the degrees of the nodes u and v in G(f), 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. (C) 2002 Elsevier B.V. All rights reserved.
引用
收藏
页码:499 / 511
页数:13
相关论文
共 19 条
  • [1] Akers S. B., 1987, Proceedings of the 1987 International Conference on Parallel Processing, P393
  • [2] A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS
    AKERS, SB
    KRISHNAMURTHY, B
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) : 555 - 566
  • [3] AKERS SB, 1987, P 2 INT C SUP, P270
  • [4] A ROUTING AND BROADCASTING SCHEME ON FAULTY STAR GRAPHS
    BAGHERZADEH, N
    NASSIF, N
    LATIFI, S
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (11) : 1398 - 1402
  • [5] BIRKHOFF G, 1965, SURVEY MODERN ALGEBR
  • [6] Chen CC, 1997, IEEE T COMPUT, V46, P1293, DOI 10.1109/12.641930
  • [7] Nearly optimal one-to-many parallel routing in star networks
    Chen, CC
    Chen, J
    [J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1997, 8 (12) : 1196 - 1202
  • [8] A COMPARATIVE-STUDY OF TOPOLOGICAL PROPERTIES OF HYPERCUBES AND STAR GRAPHS
    DAY, K
    TRIPATHI, A
    [J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1994, 5 (01) : 31 - 38
  • [9] Dietzfelbinger M., 1991, Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing (Cat. No.91TH0396-2), P400, DOI 10.1109/SPDP.1991.218213
  • [10] Galil Z., 1995, Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, P499, DOI 10.1145/225058.225267