Parallel algorithms for maximum bipartite matchings and maximum 0-1 flows

Baruch Schieber, Shlomo Moran

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Two parallel algorithms for finding maximum bipartite matchings on a CRCW PRAM are presented. The first algorithm finds a maximum bipartite matching in O(n log n) time using m processors, where n is the number of vertices and m is the number of edges in the bipartite graph. The second algorithm does the same job in O(n) time using nm processors. Simple modifications of these algorithms induce parallel algorithms for finding maximum 0-1 flows, which are also presented.

Original languageEnglish (US)
Pages (from-to)20-38
Number of pages19
JournalJournal of Parallel and Distributed Computing
Volume6
Issue number1
DOIs
StatePublished - Feb 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Parallel algorithms for maximum bipartite matchings and maximum 0-1 flows'. Together they form a unique fingerprint.

Cite this