Hamiltonian cycle problem (HCP)

Catalogue of combinatorial problems · Routing problems · Catalogue (PDF)

Definition 1: Hamiltonian cycle problem

The Hamiltonian cycle problem asks whether a graph \(G=(V,E)\) has a cycle through all its vertices.

What the course does on this problem

Technique	Where
Definition	This page
Approximation	Ch. 39 «The TSP: the general case and the metric case»
Exercises	Exercise 39.3