Hamiltonian Path Search Task
Jump to navigation
Jump to search
A Hamiltonian Path Search Task is a path search problem that requires the identification of a Hamiltonian path.
- …
- Example(s):
- Counter-Example(s):
- See: Travelling Salesman Problem, Undirected Graph, NP-Complete.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/Hamiltonian_path_problem Retrieved:2015-12-25.
- In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete. [1] There is a simple relation between the problems of finding a Hamiltonian path and a Hamiltonian cycle. In one direction, the Hamiltonian path problem for graph G is equivalent to the Hamiltonian cycle problem in a graph H obtained from G by adding a new vertex and connecting it to all vertices of G. Thus, finding a Hamiltonian path cannot be significantly slower (in the worst case, as a function of the number of vertices) than finding a Hamiltonian cycle. In the other direction, the Hamiltonian cycle problem for a graph G is equivalent to the Hamiltonian path problem in the graph H obtained by copying one vertex v of G, v', that is, letting v' have the same neighbourhood as v, and by adding two dummy vertices of degree one, and connecting them with v and v', respectively. [2]
The Hamiltonian cycle problem is also 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 circuit; if there is no Hamiltonian circuit then the shortest route will be longer).
- In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete. [1] There is a simple relation between the problems of finding a Hamiltonian path and a Hamiltonian cycle. In one direction, the Hamiltonian path problem for graph G is equivalent to the Hamiltonian cycle problem in a graph H obtained from G by adding a new vertex and connecting it to all vertices of G. Thus, finding a Hamiltonian path cannot be significantly slower (in the worst case, as a function of the number of vertices) than finding a Hamiltonian cycle. In the other direction, the Hamiltonian cycle problem for a graph G is equivalent to the Hamiltonian path problem in the graph H obtained by copying one vertex v of G, v', that is, letting v' have the same neighbourhood as v, and by adding two dummy vertices of degree one, and connecting them with v and v', respectively. [2]
- ↑ A1.3: GT37–39, pp. 199–200.
- ↑ http://math.stackexchange.com/questions/7130/reduction-from-hamiltonian-cycle-to-hamiltonian-path/1290804#1290804
2005
- (Fomin & Kaski, 2013) ⇒ Fedor V. Fomin, and Petteri Kaski. (2013). “Exact Exponential Algorithms.” In: Communications of the ACM Journal, 56(3). doi:10.1145/2428556.2428575
- QUOTE: The three problems we discuss in more detail are Maximum 2-Satisfiability, Graph Coloring, and Hamiltonian Path.