Encyclopedia > Hamiltonian cycle problem

  Article Content

Hamiltonian cycle problem

The Hamiltonian cycle or Hamiltonian circuit problem in graph theory is to find a path through a given graph which starts and ends at the same vertex and includes each vertex exactly once.

It is a special case of the traveling salesman problem, obtained by setting the distance between two cities to unity if they are adjacent and infinity otherwise. Like the traveling salesman problem, the Hamiltonian cycle problem is NP-complete.

The requirement that the path start and end at the same vertex distinguishes it from the Hamiltonian path problem.

The problem is named after Sir William Rowan Hamilton. External links



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
East Farmingdale, New York

... of 2000, there are 5,400 people, 1,693 households, and 1,286 families residing in the town. The population density is 387.5/km² (1,003.8/mi²). There are 1,723 ...

 
 
 
This page was created in 62 ms