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 -