The Hamiltonian Cycle Problem is Linear-Time Solvable for 4-Connected Planar Graphs.

Norishige Chiba Takao Nishizeki

Published in: J. Algorithms (1989)

Keyphrases

hamiltonian cycle
planar graphs
traveling salesman problem
phase transition
graph coloring
special case
np complete
connected components
minimum weight
np hard
ant colony optimization
worst case
approximate inference
computational complexity
combinatorial problems
higher order
integer programming
undirected graph