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:
“We’ve got to figure these things a little bit different than most people. Y’know, there’s something about going out in a plane that beats any other way.... A guy that washes out at the controls of his own ship, well, he goes down doing the thing that he loved the best. It seems to me that that’s a very special way to die.”
—Dalton Trumbo (1905–1976)
“The most powerful lessons about ethics and morality do not come from school discussions or classes in character building. They come from family life where people treat one another with respect, consideration, and love.”
—Neil Kurshan (20th century)