A Practical Minimum Spanning Tree Algorithm Using the Cycle Property

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.