The Hamiltonian Page

Hamiltonian cycle and path problems,
their generalizations and variations

This page intends to be a comprehensive listing of papers, source code, preprints, technical reports, etc, available on the Internet about the Hamiltonian Cycle and Hamiltonian Path Problems as well as some associated problems.

We do not provide bibliographic data for most papers listed in our page. Readers may contact the corresponding authors regarding this matter.

Please send us information about any other work you consider it should be included in this page.

Gregory Gutin's Home Page
email: gutin@dcs.rhbnc.ac.uk
email: gutin@imada.sdu.dk

Pablo Moscato's Home Page
email: moscato@densis.fee.unicamp.br
email: moscato@cacr.caltech.edu

Pages related with this one

  • TSPBIB, by Pablo Moscato.
  • Fractal Instances of the Traveling Salesman Problem, by Pablo Moscato.
  • Other NP Optimization Problems associated with Hamiltonian Cycle, by Pablo Moscato.
    Help and suggestions to improve this Java applet are really appreciated !
  • P=NP?, by Stas Busygin.

    Instances

  • Hamiltonian Cycle Problem(HCP), from TSPLIB.

    Books and Theses

  • Digraphs: Theory, Algorithms and Applications, by Joergen Bang-Jensen and Gregory Gutin, Springer-Verlag, London, October 2000.
  • Hamiltonian Path Problems in the Online-Optimization of flexible manufacturing systems, by N. Ascheuer, Ph.D.Thesis, University of Technology Berlin, Germany, 1995.
  • Finding Hamiltonian cycles: algorithms, graphs and performance, Basil Vandegriend, MSc Thesis, University of Alberta, Canada, February 1998.

    Surveys

    To help those new in the field, we established this section where we reference general surveys. This constitutes an exception to the general rule of referencing papers which are available on line, but we think it is much needed.

  • Hamiltonian cycles, by V. Chvatal, in: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B., (Eds.), The traveling salesman problem -- A guided tour of combinatorial optimization, Wiley & Sons, Chichester, 1985, 403-429.
  • Updating the Hamiltonian problem, by R.J. Gould, J. Graph Theory 15, 1991, 121-157.
  • Basic graph theory: paths and circuits, J.A. Bondy, in: Graham, R.L., Gr"otschel, M., Lovasz, L., (Eds.), Handbook of combinatorics, Vol. I (Seiten 1-1018) and II (1019-2198), North-Holland, Amsterdam, 1995, 3-110.
  • Chvatal-Erdos condition for Hamiltonian graphs, by X. Lu, J. Graph Theory 18, 1994, 791-800.
  • Cycles and paths in triangle-free graphs, by S. Brandt, in: The mathematics of Paul Erdos, Graham, Nesetril (Eds.), Springer, 1996, 32-42.
  • Paths, trees and cycles in tournaments, by J. Bang-Jensen and G. Gutin.
  • Generalizations of tournaments: A survey, by J. Bang-Jensen and G. Gutin.
  • Cycles and paths in semicomplete multipartite digraphs, theorems and algorithms: a survey, by G. Gutin.

    There is also a survey that covers the relation of Hamiltonian Cycles with Venn Diagrams, see:

  • A Survey of Venn Diagrams, by Frank Ruskey, appeared in The Electronic Journal of Combinatorics, 4 (1995).

    Software

  • Groups & Graphs, by Bill Kocay, is a software package for directed and undirected graphs, combinatorial designs, and their automorphism groups.
  • The Stony Brook Algorithm Repository, by Steven S. Skiena.
  • Finding Hamiltonian cycles: algorithms, graphs and performance, Basil Vandegriend, MSc Thesis, University of Alberta, Canada, February 1998. (contains source code for HC written in C).
  • The Informational Approach to NP Problems Solving, by Stas Busygin. (contains source code for HC written in ANSI C++). Mirror site.

    Algorithms and Complexity

  • The complexity of some problems on very sparse graphs, by Thomas Emden-Weinert, Stefan Hougardy and Bernd Kreuter, Manuscript, Humboldt-Universität zu Berlin, January 1997, submitted.
  • Complexity of searching an immobile hider in a graph, by B. von Stengel and R. Werchner, in Discrete Applied Mathematics 78 (1997), 235-249.
  • On Approximating the Longest Path in a Graph, by David Karger, Rajeev Motwani and G. Ramkumar, Algorithmica 18 (1997): 82--98 (Special Issue on Approximation Algorithms). Preliminary Version: Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science (Springer-Verlag), vol. 709, 1993, pp. 421--430. The journal submission from D. Karger's site is available here.
  • Finding hidden Hamiltonian cycles by Andrei Broder, Alan Frieze, and Eli Shamir. Published in Random Structures and Algorithms, 5:395-410, 1994.
  • Approximately Counting Hamilton Cycles in Dense Graphs, Martin Dyer, Alan Frieze and Mark Jerrum.
  • The Informational Approach to NP Problems Solving, by Stas Busygin. Mirror site.
  • Parallel algorithms for the Hamiltonian cycle and Hamiltonian problems in semi-complete bipartite digraphs, Jorgen Bang-Jensen, Mohamed El Haddad, Yannis Manoussakis, and Teresa M.Przytycka. Algorithmica 1, 1997, pp. 67-87.
  • Optimal Parallel Construction of Hamiltonian Cycles and Spanning Trees in Random Graphs, by Philip D. MacKenzie and Quentin F. Stout, (preliminary version), In Proc. 5th ACM Symp. on Parallel Algorithms and Architectures (1993), pp. 224-229.

    Phase Transitions

  • Phase Transitions in the Properties of Random Graphs, by J. Frank and C.U. Martel, Aug. 25, 1995.

    Simulated Annealing

  • Simulated Annealing Algorithm: Amelioration Techniques, by D. Delamarre and B. Virot, RAIRO-Operations Research, January 1997, to appear. Abstract and paper, from University of Orleans, France.

    Edge-coloured directed and undirected graphs

    The problem of finding a proper coloured Hamiltonian cycle in a 2-edge-coloured graph is a generalization of the Hamiltonian directed cycle problem. To see that replace every arc xy of a digraph by two edges xz and zy of colours 1 and 2, respectively.

  • Note on alternating directed cycles, by Gregory Gutin, Benjamin Sudakov, and Anders Yeo.
  • Properly colored Hamilton cycles in edge colored complete graphs, by Noga Alon and Gregory Gutin.
  • Alternating cycles and trails in 2-edge-coloured multigraphs, by Joergen Bang-Jensen and G. Gutin.
  • The complexity of some problems on very sparse graphs, by Thomas Emden-Weinert, Stefan Hougardy and Bernd Kreuter, Manuscript, Humboldt-Universität zu Berlin, January 1997.
  • The Page of Signed and Gain Graphs, by Thomas Zaslavsky.
  • A Note on Alternating Cycles in Edge-coloured Graphs, by A. Yeo.

    Digraphs

  • Quasi-hamiltonicity: a series of necessary conditions for a digraph to be hamiltonian, by G. Gutin and A. Yeo.

    Tournaments

  • Hamiltonian cycles avoiding the arcs of prescribed subtournaments, by J. Bang-Jensen, G. Gutin, and A. Yeo.
  • Paths, trees and cycles in tournaments, by J. Bang-Jensen and G. Gutin.
  • Complementary cycles containing prescribed vertices in tournaments, by J. Bang-Jensen, Y. Guo, and A. Yeo.

    Generalizations of tournaments

  • Connected $(g,f)$-factors and supereulerian digraphs, by Gregory Gutin.
  • Vertex heaviest paths and cycles in quasi-transitive digraphs, by J. Bang-Jensen and G. Gutin.
  • Paths and cycles in extended and decomposable digraphs, by J. Bang-Jensen and G. Gutin.
  • A classification of locally semicomplete digraphs, by J. Bang-Jensen, Y. Guo, G. Gutin, and L. Volkmann.
  • Finding a longest path in a complete multipartite digraph, by G. Gutin.
  • Polynomial algorithms for finding Hamiltonian paths and cycles in quasi-transitive digraphs, by G. Gutin.
  • A sufficient condition for a semicomplete multipartite digraph to be Hamiltonian, by J. Bang-Jensen, G. Gutin and J. Huang.
  • Characterizations of vertex pancyclic and pancyclic ordinary semicomplete multipartite digraphs, by G. Gutin.
  • Note on the path covering number of a semicomplete multipartite digraph, by G. Gutin and A. Yeo.
  • Weakly Hamiltonian-connected ordinary multipartite tournaments, by J. Bang-Jensen, G. Gutin and J. Huang.
  • Generalizations of tournaments: A survey, by J. Bang-Jensen and G. Gutin.
  • Cycles and paths in semicomplete multipartite digraphs, theorems and algorithms: a survey, by G. Gutin.
  • One-Diregular Subgraphs in Semicomplete Multipartite Digraphs, by A. Yeo.
  • How close to regular must a multipartite tournament be to secure Hamiltonicity?, by A. Yeo.
  • Sufficient conditions for semicomplete multipartite digraphs to be Hamiltonian, by Y. Guo, M. Tewes, L. Volkmann, and A. Yeo.

    Degree-constrained digraphs

  • Sufficient conditions for a digraph to be Hamiltonian, by J. Bang-Jensen, G. Gutin and H. Li.
  • A New Sufficient Condition for a Digraph to be Hamiltoniab, by J. Bang-Jensen, Y. Guo, and A. Yeo.

    Undirected graphs

    Planar graphs

  • Triangle graphs, by M. Benantar, U. Dogrusoz, J.E. Flaherty, and M.S. Krishnamoorthy, Journal of Applied Numerical Mathematics, 17:85-96, 1995.
  • Hamiltonian cycle problem for triangle graphs, U. Dogrusoz and M.S. Krishnamoorthy, Technical Report, 95-7, February 1995, Dept. of Computer Science, Rensselaer Polytechnic I nstitute, Troy, NY 12180, USA, Submitted for publication to Theoretical Computer Science.

    Degree-constrained graphs.

  • Simulated Annealing Algorithm: Amelioration Techniques, by D. Delamarre and B. Virot, RAIRO-Operations Research, January 1997, to appear. Abstract and paper, from University of Orleans, France.
  • Almost all cubic graphs are hamiltonian, by R. Robinson and N.C. Wormald, final version appeared in Random Structures Algorithms 3 (1992), 117-125.

    Other-parameters-constrained graphs

  • Hamiltonicity in Graphs with Few P4s, by W. Hochstättler and G. Tinhofer, ZPR 93-136.

    Other classes of undirected graphs

  • The Prism of the Acyclic Orientation Graph is Hamiltonian, by Frank Ruskey, also appears in Electronic Journal of Combinatorics, paper R5

    Random directed and undirected graphs

  • Almost all regular graphs are hamiltonian, by R. Robinson and N.C. Wormald, final version appeared in Random Structures Algorithms 5 (1994), 363-374.
  • Hamilton Cycles in Random Graphs and Digraphs, by Colin Cooper and Alan Frieze. (added May 13, 1997)

    Hypergraphs

  • Hamiltonian paths and cycles in hypertournaments, by G. Gutin and A. Yeo.

    Acknowledgements

    Many thanks to all the authors and also to Thomas Emden-Weinert, Rajeev Motwani, Bernhard von Stengel, Frank Ruskey, Andrei Broder, and Joe Culberson, who helped updating and correcting the information on this page.

    Award for this page

    Key Resource
    Links2Go Key Resource
    Algorithms Topic

    Created and maintained by:

    Pablo Moscato
    Departamento de Engenharia de Sistemas
    Faculdade de Engenharia Eletrica e de Computacao
    Universidade Estadual de Campinas
    Campinas - SP
    BRAZIL
    email: moscato@densis.fee.unicamp.br

    Prof. Z. Gregory Gutin
    Department of Computer Science
    Royal Holloway, University of London
    Egham, Surrey, TW20 0EX
    UNITED KINGDOM
    email: gutin@dcs.rhbnc.ac.uk

    Page created March 14, 1997
    Last update November 10, 2000

    Counter set to zero at noon on April 8, 1999, A.C.