Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Longest_path_problem> ?p ?o }
Showing triples 1 to 81 of
81
with 100 triples per page.
- Longest_path_problem abstract "In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or (in weighted graphs) by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard, meaning that it cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.".
- Longest_path_problem wikiPageExternalLink longestpath.mp3.
- Longest_path_problem wikiPageID "18757567".
- Longest_path_problem wikiPageLength "16549".
- Longest_path_problem wikiPageOutDegree "49".
- Longest_path_problem wikiPageRevisionID "675442277".
- Longest_path_problem wikiPageWikiLink Approximation_algorithm.
- Longest_path_problem wikiPageWikiLink Category:Computational_problems_in_graph_theory.
- Longest_path_problem wikiPageWikiLink Category:Graph_algorithms.
- Longest_path_problem wikiPageWikiLink Category:Hamiltonian_paths_and_cycles.
- Longest_path_problem wikiPageWikiLink Category:NP-complete_problems.
- Longest_path_problem wikiPageWikiLink Category:Network_theory.
- Longest_path_problem wikiPageWikiLink Circle_graph.
- Longest_path_problem wikiPageWikiLink Clique-width.
- Longest_path_problem wikiPageWikiLink Color-coding.
- Longest_path_problem wikiPageWikiLink Comparability_graph.
- Longest_path_problem wikiPageWikiLink Complement_graph.
- Longest_path_problem wikiPageWikiLink Complete_graph.
- Longest_path_problem wikiPageWikiLink Critical_path_method.
- Longest_path_problem wikiPageWikiLink Daniel_J._Barrett.
- Longest_path_problem wikiPageWikiLink Decision_problem.
- Longest_path_problem wikiPageWikiLink Depth-first_search.
- Longest_path_problem wikiPageWikiLink Directed_acyclic_graph.
- Longest_path_problem wikiPageWikiLink Distance-hereditary_graph.
- Longest_path_problem wikiPageWikiLink Dynamic_programming.
- Longest_path_problem wikiPageWikiLink Gallai–Hasse–Roy–Vitaver_theorem.
- Longest_path_problem wikiPageWikiLink Glossary_of_graph_theory.
- Longest_path_problem wikiPageWikiLink Graph_coloring.
- Longest_path_problem wikiPageWikiLink Graph_theory.
- Longest_path_problem wikiPageWikiLink Hamiltonian_path_problem.
- Longest_path_problem wikiPageWikiLink Hypercube_graph.
- Longest_path_problem wikiPageWikiLink Induced_path.
- Longest_path_problem wikiPageWikiLink Layered_graph_drawing.
- Longest_path_problem wikiPageWikiLink Longest_uncrossed_knights_path.
- Longest_path_problem wikiPageWikiLink NP-hardness.
- Longest_path_problem wikiPageWikiLink P_versus_NP_problem.
- Longest_path_problem wikiPageWikiLink Parameterized_complexity.
- Longest_path_problem wikiPageWikiLink Path_(graph_theory).
- Longest_path_problem wikiPageWikiLink Pathwidth.
- Longest_path_problem wikiPageWikiLink Planar_graph.
- Longest_path_problem wikiPageWikiLink Shortest_path_problem.
- Longest_path_problem wikiPageWikiLink Snake-in-the-box.
- Longest_path_problem wikiPageWikiLink Split_graph.
- Longest_path_problem wikiPageWikiLink Theoretical_computer_science.
- Longest_path_problem wikiPageWikiLink Time_complexity.
- Longest_path_problem wikiPageWikiLink Topological_sorting.
- Longest_path_problem wikiPageWikiLink Travelling_salesman_problem.
- Longest_path_problem wikiPageWikiLink Treewidth.
- Longest_path_problem wikiPageWikiLink Trémaux_tree.
- Longest_path_problem wikiPageWikiLinkText "Longest path problem".
- Longest_path_problem wikiPageWikiLinkText "an NP-complete problem in computer science".
- Longest_path_problem wikiPageWikiLinkText "finding the longest path".
- Longest_path_problem wikiPageWikiLinkText "longest path".
- Longest_path_problem wikiPageWikiLinkText "longest paths".
- Longest_path_problem wikiPageWikiLinkText "longest".
- Longest_path_problem wikiPageWikiLinkText "longest-path distance".
- Longest_path_problem wikiPageUsesTemplate Template:Harvtxt.
- Longest_path_problem wikiPageUsesTemplate Template:Reflist.
- Longest_path_problem subject Category:Computational_problems_in_graph_theory.
- Longest_path_problem subject Category:Graph_algorithms.
- Longest_path_problem subject Category:Hamiltonian_paths_and_cycles.
- Longest_path_problem subject Category:NP-complete_problems.
- Longest_path_problem subject Category:Network_theory.
- Longest_path_problem hypernym Problem.
- Longest_path_problem type Disease.
- Longest_path_problem type Algorithm.
- Longest_path_problem type Object.
- Longest_path_problem comment "In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or (in weighted graphs) by the sum of the weights of its edges.".
- Longest_path_problem label "Longest path problem".
- Longest_path_problem sameAs Q2916352.
- Longest_path_problem sameAs Problema_del_camí_més_llarg.
- Longest_path_problem sameAs مسئله_طولانیترین_مسیر.
- Longest_path_problem sameAs בעיית_המסלול_הארוך_ביותר.
- Longest_path_problem sameAs Ամենաերկար_ճանապարհի_խնդիր.
- Longest_path_problem sameAs Problema_do_caminho_mais_longo.
- Longest_path_problem sameAs m.03mgq6r.
- Longest_path_problem sameAs Problem_najdužeg_puta.
- Longest_path_problem sameAs ปัญหาวิถียาวสุด.
- Longest_path_problem sameAs Q2916352.
- Longest_path_problem wasDerivedFrom Longest_path_problem?oldid=675442277.
- Longest_path_problem isPrimaryTopicOf Longest_path_problem.