Skip to main content
SpringerLink
Log in

Constructing a perfect matching is in random NC

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

We show that the problem of constructing a perfect matching in a graph is in the complexity class Random NC; i.e., the problem is solvable in polylog time by a randomized parallel algorithm using a polynomial-bounded number of processors. We also show that several related problems lie in Random NC. These include:

  1. (i)

    Constructing a perfect matching of maximum weight in a graph whose edge weights are given in unary notation;

  2. (ii)

    Constructing a maximum-cardinality matching;

  3. (iii)

    Constructing a matching covering a set of vertices of maximum weight in a graph whose vertex weights are given in binary;

  4. (iv)

    Constructing a maximums-t flow in a directed graph whose edge weights are given in unary.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. D. Angluin andL. G. Valiant, Fast probabilistic algorithms for Hamiltonian circuits and matchings.J. of Comp. Syst. Sci. 18 (1979), 155–193.

    Article  MATH  MathSciNet  Google Scholar 

  2. A. Borodin, S. A. Cook andN. Pippenger, Parallel computation for well-endowed rings and space bounded probabilistic machines.Information and Control 58 (1983), 113–136.

    Article  MATH  MathSciNet  Google Scholar 

  3. A. Borodin, J. von zur Gathen andJ. Hopcroft, Fast parallel matrix and GCD computations.Proc. 23 STOC (1982), 65–71.

    Google Scholar 

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

    MATH  Google Scholar 

  5. J. Edmonds, Systems of distinct representatives and linear algebra.J. of Res. Nat. Bureau of Standards,71 A (1967), 241–245.

    MathSciNet  Google Scholar 

  6. J. Edmonds andR. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems.J. of ACM 19 (1972), 248–264.

    Article  MATH  Google Scholar 

  7. L. M. Goldschlager, R. A. Shaw andJ. Staples, The maximum flow problem is logspace complete for P.Theoretical Computer Science 21 (1982), 105–111.

    Article  MATH  MathSciNet  Google Scholar 

  8. H. J. Karloff, A Las Vegas RNC algorithm for maximum matchingCombinatorica, to appear.

  9. R. M. Karp, E. Upfal andA. Wigderson, Are search and decision problems computationally equivalent?STOC 1985.

  10. D. Kozen, U. V. Vazirani andV. V. Vazirani, The two-processors scheduling problem is in R-NC.STOC 1985.

  11. L. Lovász, Determinants, matchings and random algorithms,in: Fundamentals of Computation Theory, FCT’79. (ed. L. Budach), Akademie-Verlag Berlin 1979, pp 565–574.

  12. M. O. Rabin andV. V. Vazirani, Maximum matchings in general graphs through randomization, TR-15-84,Harvard University Center for Research in Computing Technology, 1984.

  13. J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities.J. of ACM,27 (1980), 701–717.

    Article  MATH  Google Scholar 

  14. E. Shamir andE. Upfal,N-processors graphs distributively achieve perfect matching inO(log2 N) beats.Proceeding of the First ACM SIGACT-SIGMOD Symp. on Principles of Distributed Computing. Ottawa, 1982, 238–241.

  15. W. T. Tutte, The factors of graphs.Canad. J. Math. 4 (1952), 314–328.

    MATH  MathSciNet  Google Scholar 

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

Download references

Author information

Authors and Affiliations

  1. Comp. Sci. Division, University of California, 94720, Berkeley, CA, USA

    R. M. Karp

  2. Comp. Sci. Department, Stanford University, 94305, Stanford, CA, USA

    E. Upfal

  3. IBM San Jose Res. Lab., 95193, San Jose, CA, USA

    A. Wigderson

Authors
  1. R. M. Karp
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. E. Upfal
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. A. Wigderson
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research supported by NSF Grant # DCR-8411954.

Research supported by a Weizmann Post-Doctoral fellowship, and by DARPA Grant N00039-83-C-1036.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Karp, R.M., Upfal, E. & Wigderson, A. Constructing a perfect matching is in random NC. Combinatorica 6, 35–48 (1986). https://doi.org/10.1007/BF02579407

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02579407

AMS subject classification (1980)

Search

Navigation