Hamiltonian cycle

by flyingroc

Fri Nov 10 2000 at 19:12:33

The Hamiltonian cycle problem is: given a graph, is there a simple cycle, where every vertex is visited exactly once?

This problem has been proven to be NP-complete for both directed and undirected graphs by a reduction from vertex cover. Related problems are Hamiltonian Path and the Traveling Salesman problem.

The traveling salesman problem	Hamiltonian Path	NP-complete	Hamiltonian circuit
Hamilton Circuit	vertex cover	Combinatorics	The Traveling Salesman joke
The Fall of the House of Usher	Euler tour	Euler cycle	saeculum
greedy algorithm	War of 1812	Cook's theorem	NP complexity class
Bigfoot Bonkers	pine	algorithm

Y'know, if you log in, you can write something here, or contact authors directly on the site. Create a New User if you don't already have an account.

Everything2

Login
Password