hide
Free keywords:
-
Abstract:
We describe the implementation of an algorithm which solves the
weighted matching problem in general graphs with $n$ vertices
and $m$ edges in time $O(nm \log n)$. Our algorithm is a variant
of the algorithm of Galil, Micali and Gabow [Galil et al., 1986,
SIAM J. Computing, 15, 120--130] and extensively uses
sophisticated data structures, in particular
\emph{concatenable priority queues}, so as to reduce
the time needed to perform dual adjustments and to find tight
edges in Edmonds' blossom-shrinking algorithm.
We compare our implementation to the experimentally fastest
implementation, named \emph{Blossom IV}, due to Cook and
Rohe [Cook and Rohe, Technical Report 97863, Forschungsinstitut
f{\"u}r Diskrete Mathematik, Universit{\"a}t Bonn].
Blossom IV requires only very simple data structures and
has an asymptotic running time of $O(n^2m)$.
Our experiments show that our new implementation is superior
to Blossom IV.
A closer inspection reveals that the running time of Edmonds'
blossom-shrinking algorithm in practice heavily depends on the
time spent to perform dual adjustments and to find tight edges.
Therefore, optimizing these operations, as is done in our
implementation, indeed speeds-up the practical performance of
implementations of Edmonds' algorithm.
