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.
Read more about Longest Path Problem: NP-hardness, Acyclic Graphs and Critical Paths, Approximation, Parameterized Complexity, Special Classes of Graphs, See Also
Famous quotes containing the words longest, path and/or problem:
“The longest day must have its close—the gloomiest night will wear on to a morning. An eternal, inexorable lapse of moments is ever hurrying the day of the evil to an eternal night, and the night of the just to an eternal day.”
—Harriet Beecher Stowe (1811–1896)
“My mother always used to say, “There is no path to peace. Peace is the path.””
—Donald Freed, U.S. screenwriter, and Arnold M. Stone. Robert Altman. Richard Nixon (Philip Baker Hall)
“I don’t have any problem with a reporter or a news person who says the President is uninformed on this issue or that issue. I don’t think any of us would challenge that. I do have a problem with the singular focus on this, as if that’s the only standard by which we ought to judge a president. What we learned in the last administration was how little having an encyclopedic grasp of all the facts has to do with governing.”
—David R. Gergen (b. 1942)