Module org.jgrapht.core
Package org.jgrapht.alg.tour

Class PalmerHamiltonianCycle<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    HamiltonianCycleAlgorithm<V,​E>
    public class PalmerHamiltonianCycle<V,​E>
extends HamiltonianCycleAlgorithmBase<V,​E>
    Palmer's algorithm for computing Hamiltonian cycles in graphs that meet Ore's condition. Ore gave a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with sufficiently many edges must contain a Hamilton cycle. Specifically, Ore's theorem considers the sum of the degrees of pairs of non-adjacent vertices: if every such pair has a sum that at least equals the total number of vertices in the graph, then the graph is Hamiltonian.

    A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once (Skiena 1990, p. 196).

    This is an implementation of the CRISS-CROSS algorithm described by E. M. Palmer in his paper. The algorithm takes a simple graph that meets Ore's condition (see GraphTests.hasOreProperty(Graph)) and returns a Hamiltonian cycle. The algorithm runs in $O(|V|^3)$ time and uses $O(|V|)$ space. In contrast to the most other algorithms in this package this algorithm does only attempt to find any Hamiltonian cycle in the graph and does not attempt to find the shortest cycle. The advantage of this algorithm is that accepted graphs only need to meet Ore's condition which is less strict than the completeness requirement of most of the other algorithms.

    The original algorithm is described in: Palmer, E. M. (1997), "The hidden algorithm of Ore's theorem on Hamiltonian cycles", Computers & Mathematics with Applications, 34 (11): 113–119, doi:10.1016/S0898-1221(97)00225-3 See wikipedia for a short description of Ore's theorem and Palmer's algorithm.

    Author:
    Alexandru Valeanu, Hannes Wellmann