Distributed Weighted Matching


Authors


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.