A faster deterministic algorithm for minimum spanning trees

被引：10

作者：

Chazelle, B ^{[1
]}

机构：

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

来源：

38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 1997年

关键词：

D O I：

10.1109/SFCS.1997.646089

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A deterministic algorithm for computing a minimum spanning tree of a connected graph is presented. Its running time is O(m alpha log alpha), where alpha = alpha(m, n) is a functional inverse of Ackermann's function and n (resp. m) is the number of vertices (resp. edges). This improves on the previous, ten-year old bound of (roughly) O(m log log* m).

引用

页码：22 / 34

页数：13