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:
“[In government] the problem to be solved is, not what form of government is perfect, but which of the forms is least imperfect.”
—James Madison (1751–1836)
“And weren’t there special cemetery flowers,
That, once grief sets to growing, grief may rest:
The flowers will go on with grief awhile,
And no one seem neglecting or neglected?
A prudent grief will not despise such aids.”
—Robert Frost (1874–1963)
“There are some cases ... in which the sense of injury breeds—not the will to inflict injuries and climb over them as a ladder, but—a hatred of all injury.”
—George Eliot [Mary Ann (or Marian)