The longest path problem has a polynomial solution on interval graphs
(2011)
Journal Article
Ioannidou, K., Mertzios, G., & Nikolopoulos, S. (2011). The longest path problem has a polynomial solution on interval graphs. Algorithmica, 61(2), 320-341. https://doi.org/10.1007/s00453-010-9411-3
The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamilton... Read More about The longest path problem has a polynomial solution on interval graphs.