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

Baruch Schieber, Shlomo Moran

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Pages282-292
Number of pages11
ISBN (Electronic)0897911989
DOIs
StatePublished - Nov 1 1986
Externally publishedYes
Event5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986 - Calgary, Canada
Duration: Aug 11 1986Aug 13 1986

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

Conference5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986
CountryCanada
CityCalgary
Period8/11/868/13/86

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Slowing sequential algorithms for obtaining fast distributed and parallel algorithms: Maximum matchings'. Together they form a unique fingerprint.

Cite this