Solved Special Cases
A number of important special cases of the graph isomorphism problem have efficient, polynomial-time solutions:
- Trees
- Planar graphs (In fact, planar graph isomorphism is in log space, a class contained in P.)
- Interval graphs
- Permutation graphs
- Partial k-trees
- Bounded-parameter graphs
- Graphs of bounded genus (Note: planar graphs are graphs of genus 0)
- Graphs of bounded degree
- Graphs with bounded eigenvalue multiplicity
- k-Contractible graphs (a generalization of bounded degree and bounded genus)
- Color-preserving isomorphism of colored graphs with bounded color multiplicity (i.e., at most k vertices have the same color for a fixed k) is in class NC, which is a subclass of P.
Read more about this topic: Graph Isomorphism Problem
Famous quotes containing the words solved, special and/or cases:
“Nothing in the world can take the place of Persistence. Talent will not; nothing is more common than unsuccessful men with talent. Genius will not; unrewarded genius is almost a proverb. Education will not; the world is full of educated derelicts. Persistence and Determination alone are omnipotent. The slogan “Press On”, has solved and will always solve the problems of the human race.”
—Calvin Coolidge (1872–1933)
“He’s leaving Germany by special request of the Nazi government. First he sends a dispatch about Danzig and how 10,000 German tourists are pouring into the city every day with butterfly nets in their hands and submachine guns in their knapsacks. They warn him right then. What does he do next? Goes to a reception at von Ribbentropf’s and keeps yelling for gefilte fish!”
—Billy Wilder (b. 1906)
“Only by being guilty of Folly does mortal man in many cases arrive at the perception of Sense. A thought which should forever free us from hasty imprecations upon our ever-recurring intervals of Folly; since though Folly be our teacher, Sense is the lesson she teaches; since, if Folly wholly depart from us, Further Sense will be her companion in the flight, and we will be left standing midway in wisdom.”
—Herman Melville (1819–1891)