Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An algorithm for finding hamilton paths and cycles in random graphs

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph its asymptotic probability of success is that of the existence of such a cycle. If all graphs withn vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. The algorithm HAM is also used to solve the symmetric bottleneck travelling salesman problem with probability tending to 1, asn tends to ∞.

Various modifications of HAM are shown to solve several Hamilton path problems.

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
$34.99 /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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. D. Angluin andL. G. Valiant, Fast probabilistic algorithms for Hamilton circuits and matechings,J. Computer Syst. 18, (1979), 155–193.

    Article  MATH  MathSciNet  Google Scholar 

  2. B. Bollobás, Almost all regular graphs are Hamiltonian,European Journal of Combinatorics 4, (1983), 311–316.

    Google Scholar 

  3. B. Bollobás,Random Graphs, Academic Press, London, (1985).

    MATH  Google Scholar 

  4. B. Bollobás andA. M. Frieze, On matchings and Hamilton cycles in random graphs,Annals of Discrete Mathematics,28 (1985), 23–46.

    Google Scholar 

  5. P. Erdős andA. Rényi, On the strength of connectedness of a random graph,Acta. Math. Acad. Sci. Hungar. 12, (1961), 261–267.

    Article  MathSciNet  Google Scholar 

  6. T. I. Fenner andA. M. Frieze, On the existence of Hamilton cycles in a class of random graphs.Discrete Mathematics 45, (1983), 301–305.

    Article  MATH  MathSciNet  Google Scholar 

  7. A. M. Frieze, Limit distribution for the existence of Hamiltonian cycles in a random bipartite graph,European Journal of Combinatorics,6 (1985), 327–334.

    MATH  MathSciNet  Google Scholar 

  8. Y. Gurevich andS. Shelah, Technical Report of the University of Michigan, 1985.

  9. M. Held andR. M. Karp, A dynamic programming approach to sequencing problems,SIAM Journal on Applied Mathematics 10, (1962), 196–210.

    Article  MATH  MathSciNet  Google Scholar 

  10. M. Komlós andE. Szemerédi, Limit distribution for the existence of a Hamilton cycle in a random graph,Discrete Mathematics 43, (1983), 55–63.

    Article  MATH  MathSciNet  Google Scholar 

  11. R. M. Karp andJ. M. Steele, Probabilistic analysis of the travelling salesman problem, inThe Travelling Salesman Problem: A Guided Tour (E. L. Lawler, J. K. Lenstra, A. H. G. Rinnoy-Kan and D. B. Shmoys, eds), John Wiley and Sons (1985).

  12. E. Shamir, How many edges are needed to make a random graph Hamiltonian?Combinatorica 3, (1983), 123–132.

    MATH  MathSciNet  Google Scholar 

  13. A. G. Thomason, A simple linear expected time algorithm for Hamilton cycles, to appear.

Download references

Author information

Authors and Affiliations

  1. Department of Pure Mathematics, University of Cambridge, Cambridge, England

    B. Bollobás

  2. Department of Mathematics, LSU, Baton Rouge, LA, USA

    B. Bollobás

  3. Department of Computer Science Birkbeck College, University of London, England

    T. I. Fenner

  4. Department of Computer Science Queen Mary College, University of London, England

    A. M. Frieze

  5. Department of Mathematics, Carnegie Mellon University, Pittsburgh, PA, USA

    A. M. Frieze

Authors
  1. B. Bollobás
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. T. I. Fenner
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. A. M. Frieze
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Supported by NSF Grant MCS 810 4854.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bollobás, B., Fenner, T.I. & Frieze, A.M. An algorithm for finding hamilton paths and cycles in random graphs. Combinatorica 7, 327–341 (1987). https://doi.org/10.1007/BF02579321

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

AMS subject classification

Search

Navigation