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:
“‘I mean to retire, where
Nobody will have heard about my special skills
And conversation is mainly about the wearther.”
—Eiléan Ní Chuilleanáin (b.1942)
“What’s the greatest enemy of Christianity to-day? Frozen meat. In the past only members of the upper classes were thoroughly sceptical, despairing, negative. Why? Among other reasons, because they were the only people who could afford to eat too much meat. Now there’s cheap Canterbury lamb and Argentine chilled beef. Even the poor can afford to poison themselves into complete scepticism and despair.”
—Aldous Huxley (1894–1963)