A Faster Deterministic Algorithm for Minimum Spanning Trees

A deterministic algorithm for computing a minimum spanning tree of a connected graph is presented. Its running time is O(m /spl alpha/ log /spl alpha/), where /spl alpha/=/spl 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).

Authors

• Bernard Chazelle

Keywords

• Tree graphs
• Costs
• History
• Partitioning algorithms
• Computer science
• Computational modeling
• Actual Cost
• Multiple Edges
• Red Edge
• Graph Partitioning
• Original Graph
• Single Vertex
• Single Endpoint
• Green Edges