Special Classes of Graphs
The longest path problem may be solved in polynomial time on the complements of comparability graphs. It may also be solved in polynomial time on any class of graphs with bounded treewidth or bounded clique-width, such as the distance-hereditary graphs. However, it is NP-hard even when restricted to split graphs, circle graphs, or planar graphs.
Read more about this topic: Longest Path Problem
Famous quotes containing the words special and/or classes:
“An indirect quotation we can usually expect to rate only as better or worse, more or less faithful, and we cannot even hope for a strict standard of more and less; what is involved is evaluation, relative to special purposes, of an essentially dramatic act.”
—Willard Van Orman Quine (b. 1908)
“Journalists belong in the gutter because that is where the ruling classes throw their guilty secrets.”
—Gerald Priestland (b. 1927)