V
 the graph vertex typeE
 the graph edge typepublic class PalmerHamiltonianCycle<V,E> extends Object implements HamiltonianCycleAlgorithm<V,E>
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 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^2)$ time and uses $O(V)$ space.
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/S08981221(97)002253 See wikipedia for a short description of Ore's theorem and Palmer's algorithm.
Constructor and Description 

PalmerHamiltonianCycle()
Construct a new instance

Modifier and Type  Method and Description 

GraphPath<V,E> 
getTour(Graph<V,E> graph)
Computes a Hamiltonian tour.

public GraphPath<V,E> getTour(Graph<V,E> graph)
getTour
in interface HamiltonianCycleAlgorithm<V,E>
graph
 the input graphIllegalArgumentException
 if the graph doesn't meet Ore's conditionGraphTests.hasOreProperty(Graph)
Copyright © 2020. All rights reserved.