hide
Free keywords:
-
Abstract:
We present a simple new 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 to be 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 13 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.
