Distributed Approximate Matching
Zvi Lotker, Boaz Patt-Shamir, Adi Rosén · SIAM Journal on Computing · 2009
We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a randomized $(4+\epsilon)$-approximation distributed algorithm for maximum weighted matching, whose running time is $O(\log n)$ for any constant $\epsilon>0$, where n is the number of nodes in the graph. This is, to the best of our knowledge, the first log-time distributed algorithm that achieves constant approximation for maximum weighted matching on general graphs. In addition, we consider the dynamic case, where nodes are inserted and deleted one at a time. For unweighted dynamic graphs, we give a distributed algorithm that maintains a $(1+\epsilon)$-approximation in $O(1/\epsilon)$ time for each node insertion or deletion for any constant $\epsilon>0$. For weighted dynamic graphs we give a constant-factor approximation distributed algorithm that runs in constant time for each insertion or deletion.