Distributed approximate matching Academic Article uri icon


  • 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.

publication date

  • January 1, 2009