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 want in all cases to do right.”
—Abraham Lincoln (1809–1865)