  Finding large or heavy matchings in graphs is a ubiquitous combinatorial
optimization problem. In this paper, we engineer the first non-trivial
implementations for approximating the dynamic weighted matching problem. Our
first algorithm is based on random walks/paths combined with dynamic
programming. The second algorithm has been introduced by Stubbs and Williams
without an implementation. Roughly speaking, their algorithm uses dynamic
unweighted matching algorithms as a subroutine (within a multilevel approach);
this allows us to use previous work on dynamic unweighted matching algorithms
as a black box in order to obtain a fully-dynamic weighted matching algorithm.
We empirically study the algorithms on an extensive set of dynamic instances
and compare them with optimal weighted matchings. Our experiments show that the
random walk algorithm typically fares much better than Stubbs/Williams
(regarding the time/quality tradeoff), and its results are often not far from
the optimum.
