Abstract
A deterministic algorithm for computing a minimum spanning tree of a connected graph is presented. Its running time is O(m α (m, n)), where α is the classical functional inverse of Ackermann's function and n (respectively, m) 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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1028-1047 |
| Number of pages | 20 |
| Journal | Journal of the ACM |
| Volume | 47 |
| Issue number | 6 |
| DOIs | |
| State | Published - 2000 |
All Science Journal Classification (ASJC) codes
- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence
Keywords
- Graphs
- Matroids
- Minimum spanning trees