Article

Free access

Constructing a perfect matching is in random NC

Authors:

R M Karp,

E Upfal,

A WigdersonAuthors Info & Claims

STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing

Pages 22 - 32

https://doi.org/10.1145/22145.22148

Published: 01 December 1985 Publication History

PDF eReader

References

[1]

D. Angluin and L.G. Valiant, Fast probabilistic algorithms for Hamiltonian circuits and. matchings. J. of Cornp. Syst. ScL 18, (1979) pp. 155-193.

Crossref

Google Scholar

[2]

A. Borodin, .S.A. Cook, anti N. Pippenger. Parallel computation for well-endowed rings and space bounded probabilistic machines. Information and Control 58 1-3 (1983) pp. 113-136.

Digital Library

Google Scholar

[3]

A. Borodin, J. yon zur Gathen, and J. Hopcn~ft, F:Lst parallel matrix and GCD computations. Proc. 23d STOC (1982) pp. 65-71.

Google Scholar

[4]

S.A. Cook, An overview of computation complexity. CACM 26 (1983) pp. 400-408.

Digital Library

Google Scholar

[5]

J. Edmonds, Systems of distinct representatives and linear algebra. J. of Rex NaL Bureau ofStandardx 71A (1%7)pp. 241-245.

Google Scholar

[6]

J. I:.dmonds and R.M. Karl), Theoretical improvements in alg()rithlnic efficiency for network flow problems. J. of,4CM 19 (1972) pp. 248-264.

Digital Library

Google Scholar

[7]

L.M. Goldschlager, R.A. Shaw and J. Staples. The maximum flow problem is Iogspace complete for P. Theoretical Computer Science 21 (1982)pp. 105-111.

Crossref

Google Scholar

[8]

H,J. Karloff, A randomized par~dlel algorithm for the odd-set cover problem. Submitte, d, 1985.

Google Scholar

[9]

R.M. Karp, E. Upfal and A. Wigderson, Are search and decision problems computationally equivalent? $TOC 1985.

Digital Library

Google Scholar

[10]

D. Kozen, U.V. Vazirani and V.V. Vazirani, The two-processors schcduling problem is in R-NC. $TOC 1985.

Digital Library

Google Scholar

[11]

M.O. Rabin and V.V. Vazirani, Maximum match ings in general graphs through random- Mlfion. TR-15-84, Harvard University Center for Research in Computing Technology, 1984.

Google Scholar

[12]

J.T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities.,L of ACM, 27 4 (1980) lap. 701-717.

Digital Library

Google Scholar

[13]

E. Shamir and E. Upfal, N.processors graphs distributively achieve perfect matching in O(log2N) beats. Proceeding of the Ftrst dCM $IG,4CT-SIGMOD Symp. on Princb pies of Distributed Computing Ottawa, 1982, pp. 238-241.

Digital Library

Google Scholar

[14]

W.T. Tutte, The factors of graphs. CanacL J. Math. 4 (1952) pp. 314-328.

Crossref

Google Scholar

[15]

D,J.A. Welsh, Matroid Theory. Academic Press (1976).

Google Scholar

Cited By

View all

Ghaffari MGrunau CQu JAgrawal KShun J(2023)Nearly Work-Efficient Parallel DFS in Undirected GraphsProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591094(273-283)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591094
Blikstad JVan Den Brand JEfron YMukhopadhyay SNanongkai D(2022)Nearly Optimal Communication and Query Complexity of Bipartite Matching2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00113(1174-1185)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00113
Nisan NMarx D(2021)The demand query model for bipartite matchingProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458100(592-599)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458100
Show More Cited By

Index Terms

Constructing a perfect matching is in random NC

Recommendations

Planar Graph Perfect Matching Is in NC

Is perfect matching in NC? That is, is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in theoretical computer science for over three decades, ever since the discovery of RNC perfect matching algorithms. ...
Constructing a perfect matching is in Random NC
Many-to-many perfect matching
AISS '22: Proceedings of the 4th International Conference on Advanced Information Science and System

This paper considers a new type of two-sided matching in which multiple numbers of agents are perfectly matched on both sides. Such matching can be used between multiple major students and laboratories. The many-to-many perfect matching problem cannot ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing

December 1985

484 pages

ISBN:0897911512

DOI:10.1145/22145

Chairman:
Robert Sedgewick

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1985

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC85

Sponsor:

SIGACT

STOC85: Annual ACM Conference on Theory of Computing

May 6 - 8, 1985

Rhode Island, Providence, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
801
Total Downloads

Downloads (Last 12 months)117
Downloads (Last 6 weeks)13

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ghaffari MGrunau CQu JAgrawal KShun J(2023)Nearly Work-Efficient Parallel DFS in Undirected GraphsProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591094(273-283)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591094
Blikstad JVan Den Brand JEfron YMukhopadhyay SNanongkai D(2022)Nearly Optimal Communication and Query Complexity of Bipartite Matching2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00113(1174-1185)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00113
Nisan NMarx D(2021)The demand query model for bipartite matchingProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458100(592-599)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458100
Milenković LSolomon SScheideler CSpear M(2020)A Unified Sparsification Approach for Matching Problems in Graphs of Bounded Neighborhood IndependenceProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400248(395-406)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400248
Vishnoi N(2019)Technical perspective: Isolating a matching when your coins go missingCommunications of the ACM10.1145/330621062:3(108-108)Online publication date: 21-Feb-2019
https://dl.acm.org/doi/10.1145/3306210
Campanelli MGennaro R(2017)Efficient Rational Proofs for Space Bounded ComputationsDecision and Game Theory for Security10.1007/978-3-319-68711-7_4(53-73)Online publication date: 4-Oct-2017
https://doi.org/10.1007/978-3-319-68711-7_4
Azad ABuluc A(2016)Distributed-Memory Algorithms for Maximum Cardinality Matching in Bipartite Graphs2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2016.103(32-42)Online publication date: May-2016
https://doi.org/10.1109/IPDPS.2016.103
Lotker ZPatt-Shamir BPettie S(2015)Improved Distributed Approximate MatchingJournal of the ACM10.1145/278675362:5(1-17)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.1145/2786753
Alon NNisan NRaz RWeinstein O(2015)Welfare Maximization with Limited InteractionProceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2015.95(1499-1512)Online publication date: 17-Oct-2015
https://dl.acm.org/doi/10.1109/FOCS.2015.95
Dobzinski SNisan NOren SShmoys D(2014)Economic efficiency requires interactionProceedings of the forty-sixth annual ACM symposium on Theory of computing10.1145/2591796.2591815(233-242)Online publication date: 31-May-2014
https://dl.acm.org/doi/10.1145/2591796.2591815
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Planar Graph Perfect Matching Is in NC

Constructing a perfect matching is in Random NC

Many-to-many perfect matching