Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Longest_path_problem> ?p ?o }
Showing triples 1 to 39 of
39
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 wikiPageRevisionID "602231139".
- Longest_path_problem hasPhotoCollection Longest_path_problem.
- 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 type Abstraction100002137.
- Longest_path_problem type Act100030358.
- Longest_path_problem type Action100037396.
- Longest_path_problem type Activity100407535.
- Longest_path_problem type Algorithm105847438.
- Longest_path_problem type Attribute100024264.
- Longest_path_problem type ComputationalProblemsInGraphTheory.
- Longest_path_problem type Condition113920835.
- Longest_path_problem type Course100038262.
- Longest_path_problem type Difficulty114408086.
- Longest_path_problem type Event100029378.
- Longest_path_problem type GraphAlgorithms.
- Longest_path_problem type HamiltonianPathsAndCycles.
- Longest_path_problem type NP-completeProblems.
- Longest_path_problem type Problem114410605.
- Longest_path_problem type Procedure101023820.
- Longest_path_problem type PsychologicalFeature100023100.
- Longest_path_problem type Rule105846932.
- Longest_path_problem type State100024720.
- Longest_path_problem type Way100415676.
- Longest_path_problem type YagoPermanentlyLocatedEntity.
- 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 m.03mgq6r.
- Longest_path_problem sameAs Q2916352.
- Longest_path_problem sameAs Q2916352.
- Longest_path_problem sameAs Longest_path_problem.
- Longest_path_problem wasDerivedFrom Longest_path_problem?oldid=602231139.
- Longest_path_problem isPrimaryTopicOf Longest_path_problem.