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:
“For the longest time, marriage has had a guilty conscience about itself. Should we believe it?—Yes, we should believe it.”
—Friedrich Nietzsche (1844–1900)
“In the path of an action merely typical
To create the universal, originate a symbol
Out of the impact?”
—T.S. (Thomas Stearns)
“We have heard all of our lives how, after the Civil War was over, the South went back to straighten itself out and make a living again. It was for many years a voiceless part of the government. The balance of power moved away from it—to the north and the east. The problems of the north and the east became the big problem of the country and nobody paid much attention to the economic unbalance the South had left as its only choice.”
—Lyndon Baines Johnson (1908–1973)