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

Baruch Schieber; Shlomo Moran

doi:10.1016/0743-7315(89)90040-3

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

Baruch Schieber, Shlomo Moran

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	20-38
Number of pages	19
Journal	Journal of Parallel and Distributed Computing
Volume	6
Issue number	1
DOIs	https://doi.org/10.1016/0743-7315(89)90040-3
State	Published - Feb 1989
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1016/0743-7315(89)90040-3

Cite this

@article{8400755d351b4448a2205c0453696a7b,

title = "Parallel algorithms for maximum bipartite matchings and maximum 0-1 flows",

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.",

author = "Baruch Schieber and Shlomo Moran",

year = "1989",

month = feb,

doi = "10.1016/0743-7315(89)90040-3",

language = "English (US)",

volume = "6",

pages = "20--38",

journal = "Journal of Parallel and Distributed Computing",

issn = "0743-7315",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

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

AU - Schieber, Baruch

AU - Moran, Shlomo

PY - 1989/2

Y1 - 1989/2

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

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

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

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

U2 - 10.1016/0743-7315(89)90040-3

DO - 10.1016/0743-7315(89)90040-3

M3 - Article

AN - SCOPUS:38249026359

SN - 0743-7315

VL - 6

SP - 20

EP - 38

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

IS - 1

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this