## Distributed Weighted Matching

### Authors

- Mirjam Wattenhofer, ETH Zurich
- Roger Wattenhofer, ETH Zurich

### Abstract

In this paper, we present fast
and fully distributed algorithms for matching in weighted trees and
general weighted graphs. The time complexity as well as the
approximation ratio of the tree algorithm is constant. For the general
graph algorithm we prove a constant ratio bound and a polylogarithmic
time complexity of O(\log^2 n). It was shown recently that to
constantly approximate a maximum matching locally at least \Omega(\log
\Delta/ \log \log \Delta) communication rounds are required. In light
of our result for trees, an interesting area of future research is to
investigate which classes of graphs allow constant distributed
approximations in constant time, and for which classes of graphs
constant-time algorithms experience the lower bound mentioned above.