TY - GEN

T1 - Slowing sequential algorithms for obtaining fast distributed and parallel algorithms

T2 - 5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986

AU - Schieber, Baruch

AU - Moran, Shlomo

N1 - Funding Information:
The distributed model consists of an asynchronous network, described by an undirected graph G = (V,E). The set of vertices V represents the processors of the network and the set of edges E represents the communication channels connecting them. Each vertex receives messages from its neighbors, performs local computations, and sends messages to its neighbors. Each message sent by a vertex to its neighbor arrives it within some finite, but unbounded time. The length of each message is logarithmic in the size of the network. The communication complexity of an algorithm operating in the network equals the maximum possible number of messages sent by it; the time complexity of such an algorithm is the maximum possible execution time of the t On leave from the Department of Computer Science, the Technion, Haifa 32000, Israel. :~ The research of this author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U. S. Department of Energy under contract number DE-AC02-76ER03077.
Publisher Copyright:
© 1986 ACM.

PY - 1986/11/1

Y1 - 1986/11/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=85025263736&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85025263736&partnerID=8YFLogxK

U2 - 10.1145/10590.10615

DO - 10.1145/10590.10615

M3 - Conference contribution

AN - SCOPUS:85025263736

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 282

EP - 292

BT - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

Y2 - 11 August 1986 through 13 August 1986

ER -