Slowing sequential algorithms for obtaining fast distributed and parallel algorithms: Maximum matchings

Abstract

One of the most studied problems in combinatorial optimization is the maximum matching problem. A new technique for designing algorithms for finding maximum matchings is presented. This technique is based on finding the augmenting paths without shrinking "blossoms" recursively, and on slowing the fast sequential algorithm by finding augmenting paths one at a time. The distributed algorithm obtained using this technique runs in O (n logn) time, where n is the number of vertices in the graph. The communication complexity of the distributed algorithm depends upon the model. If only constant amount of storage is available at every edge or vertex of the network then the communication complexity is O(n2m); otherwise, the communication complexity is reduced to 0(n m logn). (m is the number of edges in the graph.) No efficient distributed algorithm for this problem was known before. The same technique admits also parallel and sequential algorithms. The parallel algorithm is the most efficient deterministic parallel algorithm for this problem. The sequential algorithm is simple and does not shrink "blossoms" recursively.