Problem of finding a cycle through all vertices of a graph
This article is about the specific problem of determining whether a Hamiltonian path or cycle exists in a given graph. For the general graph theory concepts, see Hamiltonian path.
The Hamiltonian path problem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, G, contains a Hamiltonian path, a path that visits every vertex in the graph exactly once. The problem may specify the start and end of the path, in which case the starting vertex s and ending vertex t must be identified.[1]
The Hamiltonian cycle problem is similar to the Hamiltonian path problem, except it asks if a given graph contains a Hamiltonian cycle. This problem may also specify the start of the cycle. The Hamiltonian cycle problem is a special case of the travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to n. If so, the route is a Hamiltonian cycle.
The Hamiltonian path problem and the Hamiltonian cycle problem belong to the class of NP-complete problems, as shown in Michael Garey and David S. Johnson's book Computers and Intractability: A Guide to the Theory of NP-Completeness and Richard Karp's list of 21 NP-complete problems.[2][3]
^Sipser, Michael (2013). Introduction to the Theory of Computation (3rd ed.). Cengage Learning. pp. 292–314.
^Garey, Michael R; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company. p. 60.
^Held, M.; Karp, R. M. (1965). "The construction of discrete dynamic programming algorithms". IBM Systems Journal. 4 (2): 136–147. doi:10.1147/sj.42.0136. ISSN 0018-8670.
and 20 Related for: Hamiltonian path problem information
The Hamiltonianpathproblem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, G...
theory, a Hamiltonianpath (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or...
complexity of the problem; see Hamiltonianpathproblem. Another related problem is the bottleneck travelling salesman problem: Find a Hamiltonian cycle in a...
solve a problem of optimal control for a dynamical system Hamiltonianpath, a path in a graph that visits each vertex exactly once Hamiltonian group, a...
and only if there is a Hamiltonianpath in G. The Hamiltonianpathproblem is NP-complete, and hence the minimum path cover problem is NP-hard. However,...
unique ordering exists, and whether a Hamiltonianpath exists, despite the NP-hardness of the Hamiltonianpathproblem for more general directed graphs (i...
use of DNA as a form of computation which solved the seven-point Hamiltonianpathproblem. Since the initial Adleman experiments, advances have occurred...
linguistic structure. Hamiltonianpathproblem Minimum spanning tree Route inspection problem (also called the "Chinese postman problem") Seven bridges of...
Hamiltonian simulation (also referred to as quantum simulation) is a problem in quantum information science that attempts to find the computational complexity...
such as the Boolean satisfiability problem, the Hamiltonianpathproblem and the vertex cover problem. Since deterministic Turing machines are special...
to program E. coli to solve complicated mathematics problems, such as the Hamiltonianpathproblem. A computer to control protein production of E. coli...
enters the path integrals (for interactions of a certain type, these are coordinate space or Feynman path integrals), than the Hamiltonian. Possible downsides...
traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. The problem is to find the Hamiltonian cycle (visiting...
first problem attacked in this way was the Hamiltonianpathproblem. The simplest one is the subset sum problem. An optical device solving an instance with...
odd-degree vertices Hamiltonianpath – a path that visits each vertex exactly once. Route inspection problem, search for the shortest path that visits all...
The Hamiltonian completion problem is to find the minimal number of edges to add to a graph to make it Hamiltonian. The problem is clearly NP-hard in...
Global Information