Distributed weighted matching
Mirjam Wattenhofer, Roger P. Wattenhofer · Repository for Publications and Research Data (ETH Zurich) · 2003
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. In particular, the approximation ratio is 4. For the general graph algorithm we prove a constant ratio bound of 5 and a polylogarithmic time complexity of O(log2 n).