Efficient Distributed Weighted Matchings on Trees
Jaap-Henk Hoepman,Shay Kutten and Zvi Lotker
Abstract:
In this paper, we study distributed algorithms to compute a weighted matching that have
constant (or at least sub-logarithmic) running time and that achieve approximation ratio
2 + ? or better. In fact we present two such synchronous algorithms, that work on arbitrary
weighted trees.
The first algorithm is a randomised distributed algorithm that computes a weighted matching
of an arbitrary weighted tree, that approximates the maximum weighted matching by a factor
2 + ?. The running time is O(1). The second algorithm is deterministic, and approximates
the maximum weighted matching by a factor 2 + ?, but has running time O(log* |V|). Our
algorithms can also be used to compute maximum unweighted matchings on regular and almost
regular graphs within a constant approximation.