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:
“The problems of this world are only truly solved in two ways: by extinction or duplication.”
—Susan Sontag (b. 1933)
“Personal prudence, even when dictated by quite other than selfish considerations, surely is no special virtue in a military man; while an excessive love of glory, impassioning a less burning impulse, the honest sense of duty, is the first.”
—Herman Melville (1819–1891)
“I do not believe in lawyers, in that mode of attacking or defending a man, because you descend to meet the judge on his own ground, and, in cases of the highest importance, it is of no consequence whether a man breaks a human law or not. Let lawyers decide trivial cases.”
—Henry David Thoreau (1817–1862)