@inproceedings{1fcdc9508c4d45819ee3e2f84a659b23,
title = "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.",
author = "Baruch Schieber and Shlomo Moran",
note = "Publisher Copyright: {\textcopyright} 1986 ACM.; 5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986 ; Conference date: 11-08-1986 Through 13-08-1986",
year = "1986",
month = nov,
day = "1",
doi = "10.1145/10590.10615",
language = "English (US)",
series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",
publisher = "Association for Computing Machinery",
pages = "282--292",
booktitle = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",
}