Efficient distributed weighted matchings on trees Conference Paper uri icon

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.

publication date

  • January 1, 2006