Package org.graph4j.hamiltonian

Class PalmerHamiltonianCycle

java.lang.Object
org.graph4j.SimpleGraphAlgorithm
org.graph4j.hamiltonian.PalmerHamiltonianCycle
All Implemented Interfaces:
HamiltonianCycleAlgorithm
public class PalmerHamiltonianCycle extends SimpleGraphAlgorithm implements HamiltonianCycleAlgorithm
The algorithm finds a Hamiltonian cycle in an undirected simple graph that satisfies Ore's condition: deg(v) + deg(u) >= |V(G)|, for every pair of distinct non-adjacent vertices v and u. The Ore's condition is not tested explicitly - if the algorithm fails to identify a hamiltonian cycle, using Palmer's alorithm, it returns null. Reference: Palmer, E. M. (1997), "The hidden algorithm of Ore's theorem on Hamiltonian cycles".
Author:
Cristian Frăsinaru

  • Constructor Details

    • PalmerHamiltonianCycle

      public PalmerHamiltonianCycle(Graph graph)

  • Method Details

    • findCycle

      public Cycle findCycle()
      Specified by:
      findCycle in interface HamiltonianCycleAlgorithm
      Returns:
      an Hamiltonian cycle, or null if the graph does not contain one or the algorithm is unable to find it.