# 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

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