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.

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

Gregory Gutin's Home Page
email: Z.G.Gutin@brunel.ac.uk
email: gutin@imada.ou.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. The page contains an interesting discussion on the recent claims on Anatoly Plotnikov's algorithm for Hamiltonian Cycle. We thank both of them for providing pointers to their work. Mirror site.

    Instances

  • Hamiltonian Cycle Problem(HCP), from TSPLIB.

    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 digraphs, combinatorial designs, and their automorphism groups. Some of the features alredy in version 2.4.1. are: Visual graph/digraph editor; Automorphism group computation; Graph certificate which identifies a graph uniquely up to isomorphism; Hamiltonian cycles; Planarity test and planar layout; Line graphs, neighbour graphs, bipartite doubles; High quality PostScript output of graphs and digraphs; Display of orbits, generators, and elements of permutation groups; Block systems, commutator subgroups, stabilisers.
  • 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.

    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. Submitted.
  • 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.
  • The Page of Signed and Gain Graphs, by Thomas Zaslavsky, contains ``a bibliography of the mathematics of signed and gain graphs and allied areas. It includes subjects like bidirected graphs, networks with gains, arrangements of hyperplanes related to root systems; results from physics, chemistry, and social science'', etc,
  • A Note on Alternating Cycles in Edge-coloured Graphs, by A. Yeo.

    Digraphs.

  • Hamilton Cycles in Random Graphs and Digraphs, by Colin Cooper and Alan Frieze. (added May 13, 1997)
  • 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.

    Other-parameters-constrained digraphs.

    Other classes of digraphs.

    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.

    Degree-constrained graphs - Cubic 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.

    Perfect graphs.

    Other classes of graphs.

    Random 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.

    Hypergraphs

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

    Thesis

  • 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.

    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.

    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

    Dr. Z. Gregory Gutin
    Department of Mathematics and Statistics
    Brunel University of West London
    Uxbridge, Middx
    UB8 3PH
    UNITED KINGDOM
    email: Z.G.Gutin@brunel.ac.uk

    Page created March 14, 1997
    Last update June 15, 1998

    Counter set to zero at Jun. 24, 1998, A.C.