A minimum spanning tree algorithm with Inverse Ackermann type complexity

被引：177

作者：

Chazelle, B ^{[1
]}

机构：

[1] Princeton Univ, Dept Comp Sci, Princeton, NJ 08544 USA

来源：

JOURNAL OF THE ACM | 2000年 / 47卷 / 06期

关键词：

theory; graphs; matroids; minimum spanning trees;

D O I：

10.1145/355541.355562

中图分类号：

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

学科分类号：

0812 ;

摘要：

A deterministic algorithm for computing a minimum spanning tree of a connected graph is presented. Its running time is O(m alpha (m, n)), where alpha is the classical functional inverse of Ackermann's function and n (respectively, in) is the number of vertices (respectively, edges). The algorithm is comparison-based: it uses pointers, not arrays, and it makes no numeric assumptions on the edge costs.

引用

页码：1028 / 1047

页数：20

共 18 条

[1]

[Anonymous], 1926, Prace Mor. Prfrodoved. Spol. V Brne III

[2] THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE [J].

Chazelle, Bernard ;

Rosenberg, Burton .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1991, 1 (01) :33-45

[3]

Chazelle Bernard, 2000, J ACM, V47

[4]

Cheriton D., 1976, SIAM Journal on Computing, V5, P724, DOI 10.1137/0205051

[5] 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

[6] SURPASSING THE INFORMATION-THEORETIC BOUND WITH FUSION TREES [J].

FREDMAN, ML ;

WILLARD, DE .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1993, 47 (03) :424-436

[7] FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS [J].

FREDMAN, ML ;

TARJAN, RE .

JOURNAL OF THE ACM, 1987, 34 (03) :596-615

[8] EFFICIENT ALGORITHMS FOR FINDING MINIMUM SPANNING-TREES IN UNDIRECTED AND DIRECTED-GRAPHS [J].

GABOW, HN ;

GALIL, Z ;

SPENCER, T ;

TARJAN, RE .

COMBINATORICA, 1986, 6 (02) :109-122

[9]

GRAHAM RL, 1985, ANN HIST COMPUT, V7, P43

[10] A RANDOMIZED LINEAR-TIME ALGORITHM TO FIND MINIMUM SPANNING-TREES [J].

KARGER, DR ;

KLEIN, PN ;

TARJAN, RE .

JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 1995, 42 (02) :321-328

← 1 2 →