EFFICIENT ALGORITHMS FOR FINDING MINIMUM SPANNING-TREES IN UNDIRECTED AND DIRECTED-GRAPHS

被引:321
作者
GABOW, HN
GALIL, Z
SPENCER, T
TARJAN, RE
机构
[1] UNIV COLORADO,BOULDER,CO 80309
[2] COLUMBIA UNIV,NEW YORK,NY 10027
[3] AT&T BELL LABS,MURRAY HILL,NJ 07974
[4] TEL AVIV UNIV,IL-69978 TEL AVIV,ISRAEL
[5] RENSSELAER POLYTECH INST,TROY,NY 12180
关键词
D O I
10.1007/BF02579168
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
引用
收藏
页码:109 / 122
页数:14
相关论文
共 21 条
  • [1] Bock, 1971, DEV OPERATIONS RES, P29
  • [2] Boruvka O., 1926, PRACE MORAVSKE PRIRO, V3, P37
  • [3] NOTE ON FINDING OPTIMUM BRANCHINGS
    CAMERINI, PM
    FRATTA, L
    MAFFIOLI, F
    [J]. NETWORKS, 1979, 9 (04) : 309 - 312
  • [4] Cheriton D., 1976, SIAM Journal on Computing, V5, P724, DOI 10.1137/0205051
  • [5] CHU YJ, 1965, SCI SINICA, V14, P1396
  • [6] OPTIMUM BRANCHINGS
    EDMONDS, J
    [J]. JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICAL SCIENCES, 1967, B 71 (04): : 233 - +
  • [7] Fredman M. L., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P338, DOI 10.1109/SFCS.1984.715934
  • [8] FREDMAN ML, IN PRESS J ASS COMPU
  • [9] Gabow H. N., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P347, DOI 10.1109/SFCS.1984.715935
  • [10] EFFICIENT ALGORITHMS FOR A FAMILY OF MATROID INTERSECTION PROBLEMS
    GABOW, HN
    TARJAN, RE
    [J]. JOURNAL OF ALGORITHMS, 1984, 5 (01) : 80 - 131