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:
“America is a great country. It has many shortcomings, many social inequalities, and it’s tragic that the problem of the blacks wasn’t solved fifty or even a hundred years ago, but it’s still a great country, a country full of opportunities, of freedom! Does it seem nothing to you to be able to say what you like, even against the government, the Establishment?”
—Golda Meir (1898–1978)
“Research shows clearly that parents who have modeled nurturant, reassuring responses to infants’ fears and distress by soothing words and stroking gentleness have toddlers who already can stroke a crying child’s hair. Toddlers whose special adults model kindliness will even pick up a cookie dropped from a peer’s high chair and return it to the crying peer rather than eat it themselves!”
—Alice Sterling Honig (20th century)
“Colonel, never go out to meet trouble. If you will just sit still, nine cases out of ten someone will intercept it before it reaches you.”
—Calvin Coolidge (1872–1933)