Name
Abstract | ||
|---|---|---|
We present a simple new (randomized) algorithm for computing minimum spanning trees that is more than two times faster than the best previously known algorithms (for dense, "difficult" inputs). It is of conceptual interest that the algorithm uses the property that the heaviest edge in a cycle can be discarded. Previously this has only been exploited in asymptotically optimal algorithms that are considered impractical. An additional advantage is that the algorithm can greatly profit from pipelined memory access. Hence, an implementation on a vector machine is up to 10 times faster than previous algorithms. We outline additional refinements for MSTs of implicitly defined graphs and the use of the central data structure for querying the heaviest edge between two nodes in the MST. The latter result is also interesting for sparse graphs. |
Year | Venue | Keywords |
|---|---|---|
2003 | ALGORITHMS - ESA 2003, PROCEEDINGS | minimum spanning tree,randomized algorithm |
Field | DocType | Volume |
Randomized algorithm,Expected linear time MST algorithm,Combinatorics,Distributed minimum spanning tree,Algorithmics,Computer science,Algorithm,Spanning tree,Asymptotically optimal algorithm,Dense graph,Minimum spanning tree | Conference | 2832 |
ISSN | Citations | PageRank |
0302-9743 | 12 | 0.80 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irit Katriel | 1 | 176 | 13.72 |
| Peter Sanders | 2 | 1957 | 120.14 |
| Jesper Larsson Träff | 3 | 845 | 94.16 |