Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Hamiltonian_path_problem> ?p ?o }
Showing triples 1 to 64 of
64
with 100 triples 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, 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.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 wikiPageLength "10753".
- Hamiltonian_path_problem wikiPageOutDegree "31".
- Hamiltonian_path_problem wikiPageRevisionID "705395047".
- Hamiltonian_path_problem wikiPageWikiLink Barnettes_conjecture.
- Hamiltonian_path_problem wikiPageWikiLink Big_O_notation.
- Hamiltonian_path_problem wikiPageWikiLink Bipartite_graph.
- Hamiltonian_path_problem wikiPageWikiLink Brute-force_search.
- Hamiltonian_path_problem wikiPageWikiLink Category:Computational_problems_in_graph_theory.
- Hamiltonian_path_problem wikiPageWikiLink Category:Hamiltonian_paths_and_cycles.
- Hamiltonian_path_problem wikiPageWikiLink Category:NP-complete_problems.
- Hamiltonian_path_problem wikiPageWikiLink Christos_Papadimitriou.
- Hamiltonian_path_problem wikiPageWikiLink Complete_graph.
- Hamiltonian_path_problem wikiPageWikiLink Complexity_class.
- Hamiltonian_path_problem wikiPageWikiLink DNA_computing.
- Hamiltonian_path_problem wikiPageWikiLink Decision_problem.
- Hamiltonian_path_problem wikiPageWikiLink Directed_graph.
- Hamiltonian_path_problem wikiPageWikiLink Dynamic_programming.
- Hamiltonian_path_problem wikiPageWikiLink FNP_(complexity).
- Hamiltonian_path_problem wikiPageWikiLink Graph_(discrete_mathematics).
- Hamiltonian_path_problem wikiPageWikiLink Graph_theory.
- Hamiltonian_path_problem wikiPageWikiLink Hamiltonian_path.
- Hamiltonian_path_problem wikiPageWikiLink Handshaking_lemma.
- Hamiltonian_path_problem wikiPageWikiLink Inclusion–exclusion_principle.
- Hamiltonian_path_problem wikiPageWikiLink Karps_21_NP-complete_problems.
- Hamiltonian_path_problem wikiPageWikiLink Leonard_Adleman.
- Hamiltonian_path_problem wikiPageWikiLink Mathematics.
- Hamiltonian_path_problem wikiPageWikiLink Monte_Carlo_algorithm.
- Hamiltonian_path_problem wikiPageWikiLink NP-completeness.
- Hamiltonian_path_problem wikiPageWikiLink PPA_(complexity).
- Hamiltonian_path_problem wikiPageWikiLink Planar_graph.
- Hamiltonian_path_problem wikiPageWikiLink Regular_graph.
- Hamiltonian_path_problem wikiPageWikiLink Travelling_salesman_problem.
- Hamiltonian_path_problem wikiPageWikiLinkText "Directed Hamilton circuit".
- Hamiltonian_path_problem wikiPageWikiLinkText "Hamiltonian circuit problem".
- Hamiltonian_path_problem wikiPageWikiLinkText "Hamiltonian cycle".
- Hamiltonian_path_problem wikiPageWikiLinkText "Hamiltonian path problem".
- Hamiltonian_path_problem wikiPageWikiLinkText "Hamiltonian path".
- Hamiltonian_path_problem wikiPageWikiLinkText "Undirected Hamilton circuit".
- Hamiltonian_path_problem wikiPageWikiLinkText "hamiltonian path problem".
- Hamiltonian_path_problem wikiPageUsesTemplate Template:About.
- Hamiltonian_path_problem wikiPageUsesTemplate Template:Commons_category_inline.
- Hamiltonian_path_problem wikiPageUsesTemplate Template:Reflist.
- 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 hypernym Problems.
- Hamiltonian_path_problem type Disease.
- Hamiltonian_path_problem type Object.
- Hamiltonian_path_problem type Redirect.
- 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 sameAs Q987652.
- 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 Проблем_Хамилтоновог_пута.
- Hamiltonian_path_problem sameAs Hamilton_yolu_problemi.
- Hamiltonian_path_problem sameAs Q987652.
- Hamiltonian_path_problem sameAs 哈密頓路徑問題.
- Hamiltonian_path_problem wasDerivedFrom Hamiltonian_path_problem?oldid=705395047.
- Hamiltonian_path_problem isPrimaryTopicOf Hamiltonian_path_problem.