Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Hamiltonian_path_problem> ?p ?o. }
Showing items 1 to 38 of
38
with 100 items per page.
- Hamiltonian_path_problem abstract "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.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, a graph G has a Hamiltonian cycle using edge uv if and only if the graph H obtained from G by replacing the edge by a pair of vertices of degree 1, one connected to u and one connected to v, has a Hamiltonian path. Therefore, by trying this replacement for all edges incident to some chosen vertex of G, the Hamiltonian cycle problem can be solved by at most n Hamiltonian path computations, where n is the number of vertices in the graph.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).".
- Hamiltonian_path_problem wikiPageID "149646".
- Hamiltonian_path_problem wikiPageRevisionID "605246372".
- Hamiltonian_path_problem hasPhotoCollection Hamiltonian_path_problem.
- Hamiltonian_path_problem subject Category:Computational_problems_in_graph_theory.
- Hamiltonian_path_problem subject Category:Hamiltonian_paths_and_cycles.
- Hamiltonian_path_problem subject Category:NP-complete_problems.
- Hamiltonian_path_problem type Abstraction100002137.
- Hamiltonian_path_problem type Act100030358.
- Hamiltonian_path_problem type Action100037396.
- Hamiltonian_path_problem type Attribute100024264.
- Hamiltonian_path_problem type ComputationalProblemsInGraphTheory.
- Hamiltonian_path_problem type Condition113920835.
- Hamiltonian_path_problem type Course100038262.
- Hamiltonian_path_problem type Difficulty114408086.
- Hamiltonian_path_problem type Event100029378.
- Hamiltonian_path_problem type HamiltonianPathsAndCycles.
- Hamiltonian_path_problem type NP-completeProblems.
- Hamiltonian_path_problem type Problem114410605.
- Hamiltonian_path_problem type PsychologicalFeature100023100.
- Hamiltonian_path_problem type State100024720.
- Hamiltonian_path_problem type Way100415676.
- Hamiltonian_path_problem type YagoPermanentlyLocatedEntity.
- Hamiltonian_path_problem comment "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.There is a simple relation between the problems of finding a Hamiltonian path and a Hamiltonian cycle.".
- Hamiltonian_path_problem label "Hamiltonian path problem".
- Hamiltonian_path_problem label "Problema del camino Hamiltoniano".
- Hamiltonian_path_problem label "Problema do caminho hamiltoniano".
- Hamiltonian_path_problem label "ハミルトン閉路問題".
- Hamiltonian_path_problem label "哈密頓路徑問題".
- Hamiltonian_path_problem sameAs Problema_del_camino_Hamiltoniano.
- Hamiltonian_path_problem sameAs ハミルトン閉路問題.
- Hamiltonian_path_problem sameAs Problema_do_caminho_hamiltoniano.
- Hamiltonian_path_problem sameAs m.01376m.
- Hamiltonian_path_problem sameAs Q987652.
- Hamiltonian_path_problem sameAs Q987652.
- Hamiltonian_path_problem sameAs Hamiltonian_path_problem.
- Hamiltonian_path_problem wasDerivedFrom Hamiltonian_path_problem?oldid=605246372.
- Hamiltonian_path_problem isPrimaryTopicOf Hamiltonian_path_problem.