Improved processor bounds for combinatorial problems in RNC | Combinatorica
Skip to main content
Springer Nature Link
Log in

Improved processor bounds for combinatorial problems in RNC

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

Our main result improves the known processor bound by a factor ofn 4 (maintaining the expected parallel running time,O(log3 n)) for the following important problem:find a perfect matching in a general or in a bipartite graph with n vertices. A solution to that problem is used in parallel algorithms for several combinatorial problems, in particular for the problems of finding i) a (perfect) matching of maximum weight, ii) a maximum cardinality matching, iii) a matching of maximum vertex weight, iv) a maximums-t flow in a digraph with unit edge capacities. Consequently the known algorithms for those problems are substantially improved.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Berkowitz, On Computing the Determinant in Small Parallel Time Using a Small Number of Processors,Information Processing Letters.18 (1984), 147–150.

    Google Scholar 

  2. A. Borodin, S. Cook andN. Pippenger, Parallel Computation for Well-Endowed Rings and and Space-Bounded Probabilistic Machines,Inform, and Control,58 (1983), 113–136.

    Google Scholar 

  3. A. Borodin, J. von zur Gathen andJ. Hopcroft, Fast Parallel Matrix and GCD Computations,Inform. and Control,53 (1982), 241–256.

    Google Scholar 

  4. A.Broder,private communication, 1985.

  5. D.Coppersmith and S.Winograd, Matrix Multiplication via Arithmetic Progressions,Proc. 19th Ann. ACM Symp. on Theory of Computing, 1987, 1–6.

  6. H.Gabow,private communication, 1985.

  7. R. M.Karp, E.Uffal and A.Wigderson, Constructing a Perfect Matching Is in Random NC,Proc. 17-th Ann. ACM Symp. on Theory of Computing, (1985), 22–32.

  8. M. Marcus andH. Minc,A Survey of Matrix Theory and Matrix Inequalities, Allyn and Bacon, Boston, 1964.

    Google Scholar 

  9. K. Mulmuley, U. Vazirani andV. Vazirani, Matching Is As Easy As Matrix Inversion,Combinatorica,7 (1987), 105–114.

    Google Scholar 

  10. V. Pan, Fast and Efficient Parallel Algorithms for Exact Inversion of Integer Matrices,Proc. Fifth Conf. on Software Technology and Theoretical Computer Science, Computer Science,206 (1985), 504–521; Complexity of Parallel Matrix Computations,Theoretical Computer Science,54 (1987) (to appear).

    Google Scholar 

  11. F. P. Preparata andD. V. Sarwate, An Improved Parallel Processor Bound in Fast Matrix Inversion,Inform. Proc. Letters,7 (1978), 148–149.

    Google Scholar 

  12. M. O.Rabin and V.Vazirani, Maximum Matchings in Graphs through RandomizationTech. Report TR-I5-84, Center for Research in Computer Technology, Aiken Computation Laboratory, Harvard University, 1984.

  13. J. E. Savage,The Complexity of Computing, John Wiley and Sons, N.Y., 1976.

    Google Scholar 

  14. J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities,J. of ACM,27 (1980), 701–717.

    Google Scholar 

  15. D. Y. Y.Yun, Algebraic Algorithms Usingp-adic Constructions,Proc. 1976 ACM Symp, Symbolic and Algebraic Computation, (1976), 248–259.

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Columbia University, USA

    Z. Galil

  2. Tel-Aviv University, Israel

    Z. Galil

  3. Computer Science Department, State University of New York at Albany, USA

    V. Pan

Authors
  1. Z. Galil
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. V. Pan
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Partially supported by NSF Grants MCS 8303139 and DCR 8511713.

Supporeted by NSF Grants MCS 8203232 and DCR 8507573.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Galil, Z., Pan, V. Improved processor bounds for combinatorial problems in RNC. Combinatorica 8, 189–200 (1988). https://doi.org/10.1007/BF02122800

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

AMS subject classification(1980)

Search

Navigation