A RANDOMIZED LINEAR-TIME ALGORITHM TO FIND MINIMUM SPANNING-TREES

被引：236

作者：

KARGER, DR

KLEIN, PN

TARJAN, RE

机构：

[1] STANFORD UNIV,STANFORD,CA 94305

[2] BROWN UNIV,DEPT COMP SCI,PROVIDENCE,RI 02912

[3] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544

[4] NEC CORP LTD,RES INST,PRINCETON,NJ

来源：

JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY | 1995年 / 42卷 / 02期

关键词：

MATROID; MINIMUM SPANNING TREE; NETWORK; RANDOMIZED ALGORITHM;

D O I：

10.1145/201019.201022

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons.

引用

页码：321 / 328

页数：8

共 23 条

[1]

ALON N, 1992, PROBABILISTIC METHOD, P223

[2]

Boruvka O, 1926, PRACE MOR PRIRODOVED, V3, P37

[3]

CHERIYAN J, 1990, LECT NOTES COMPUT SC, V443, P235

[4] A MEASURE OF ASYMPTOTIC EFFICIENCY FOR TESTS OF A HYPOTHESIS BASED ON THE SUM OF OBSERVATIONS [J].

CHERNOFF, H .

ANNALS OF MATHEMATICAL STATISTICS, 1952, 23 (04) :493-507

[5]

Cole R., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P478, DOI 10.1109/SFCS.1986.10

[6]

COLE R, 1994, 6TH P S PAR ALGOR AR, P11

[7] VERIFICATION AND SENSITIVITY ANALYSIS OF MINIMUM SPANNING-TREES IN LINEAR TIME [J].

DIXON, B ;

RAUCH, M ;

TARJAN, RE .

SIAM JOURNAL ON COMPUTING, 1992, 21 (06) :1184-1192

[8]

Feller W., 1968, INTRO PROBABILITY TH, V1

[9]

FREDMAN ML, 1990, 31ST P FOCS, P719

[10]

Gabow H. N., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P347, DOI 10.1109/SFCS.1984.715935

← 1 2 3 →