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:
“When we walk the streets at night in safety, it does not strike us that this might be otherwise. This habit of feeling safe has become second nature, and we do not reflect on just how this is due solely to the working of special institutions. Commonplace thinking often has the impression that force holds the state together, but in fact its only bond is the fundamental sense of order which everybody possesses.”
—Georg Wilhelm Friedrich Hegel (1770–1831)
“There were three classes of inhabitants who either frequent or inhabit the country which we had now entered: first, the loggers, who, for a part of the year, the winter and spring, are far the most numerous, but in the summer, except for a few explorers for timber, completely desert it; second, the few settlers I have named, the only permanent inhabitants, who live on the verge of it, and help raise supplies for the former; third, the hunters, mostly Indians, who range over it in their season.”
—Henry David Thoreau (1817–1862)