An optimal minimum spanning tree algorithm

By Seth Pettie, V. Ramachandran. JACM, 2000

364 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/9d2796bba8813e29013ba9874cd125aba9b8748f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Steven S. Skiena
2. Bang Ye Wu
3. Kun-Mao Chao
4. Michael D. Linderman
5. Kevin P. Murphy
6. Louis H. Rowen
7. Zur Izhakian
8. Sanjit A. Seshia

In Electrical and Electronic Engineering

1. Jennifer C. Hou
2. Steven S. Skiena
3. Bang Ye Wu
4. Kun-Mao Chao
5. Lui Raymond Sha
6. Bang Wang

Citations in the corpus

• Design and analysis of an MST-based topology control algorithm (2003, background): “The time complexity varies from (the original Prim’s algorithm [15]) to almost linear of (the optimal algorithm [ 16 ]), where is the number of edges and is the number of vertices.”
• The Algorithm Design Manual (2020, background): “[PR02] S. Pettie and V. Ramachandran.”
• Extracting a Cellular Hierarchy from High-dimensional Cytometry Data with SPADE (2011, positive): “(iii) Minimum spanning tree construction— SPADE uses Boruvka’s algorithm [23] to construct a minimum spanning tree (MST) that links the cell clusters.”
• Spanning trees and optimization problems (2004, background): “U ← {r} while |U | n do Find u ∈ U and v ∈ V − U such that the edge (u, v) is a smallest edge between U and V − U .”