Output details

The longest path problem has a polynomial solution on interval graphs

<13>The dynamic programming algorithm of this paper has attracted the research interest of Dr. Ivona Bezakova and Professor Derek Corneil. Within these two subsequent collaborations we successfully extended this technique to circular-arc graphs [Mertzios and Bezakova, Computing and counting the longest paths on circular-arc graphs in polynomial time, Discrete Applied Mathematics. To appear] and to co-comparability graphs [Mertzios and Corneil, A simple polynomial algorithm for the longest path problem on cocomparability graphs, SIAM Journal on Discrete Mathematics, 26(3), 2012, pages 940-963] (in both papers, explicit references are given in the Abstract and Introduction).