@conference{OSS09,
author = "Vitaly Osipov and Peter Sanders and Johannes Singler",
abstract = "We present Filter-Kruskal - a simple modification of Kruskal's algorithm
that avoids sorting edges that are "obviously" not in the MST. For
arbitrary graphs with random edge weights Filter-Kruskal runs in time
$\Oh{m + n\log n\log\frac{m}{n}}$, i.e. in linear time for not too
sparse graphs. Experiments indicate that the algorithm has very good practical performance over the entire range of
edge densities. An equally simple parallelization seems to be the currently best
practical algorithm on multicore machines.",
address = " ",
booktitle = "10th Workshop on Algorithm Engineering and Experiments (ALENEX)",
crossref = " ",
editor = " ",
month = " ",
number = " ",
organization = " ",
pages = "52--61",
publisher = " ",
series = " ",
title = "{T}he {F}ilter-{K}ruskal {M}inimum {S}panning {T}ree {A}lgorithm",
url = "http://www.siam.org/proceedings/alenex/2009/alx09_005_osipovv.pdf",
volume = " ",
year = "2009",
}