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:
“Daisies in water are the longest lasting
flower you can give to someone.
Fact.
Buy daisies.
Not roses.”
—Anne Sexton (1928–1974)
“... my aim is now, as it has been for the past ten years, to make myself a true woman, one worthy of the name, and one who will unshrinkingly follow the path which God marks out, one whose aim is to do all of the good she can in the world and not be one of the delicate little dolls or the silly fools who make up the bulk of American women, slaves to society and fashion.”
—Ellen Henrietta Swallow Richards (1842–1911)
“Give a scientist a problem and he will probably provide a solution; historians and sociologists, by contrast, can offer only opinions. Ask a dozen chemists the composition of an organic compound such as methane, and within a short time all twelve will have come up with the same solution of CH4. Ask, however, a dozen economists or sociologists to provide policies to reduce unemployment or the level of crime and twelve widely differing opinions are likely to be offered.”
—Derek Gjertsen, British scientist, author. Science and Philosophy: Past and Present, ch. 3, Penguin (1989)