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)
“We agree fully that the mother and unborn child demand special consideration. But so does the soldier and the man maimed in industry. Industrial conditions that are suitable for a stalwart, young, unmarried woman are certainly not equally suitable to the pregnant woman or the mother of young children. Yet “welfare” laws apply to all women alike. Such blanket legislation is as absurd as fixing industrial conditions for men on a basis of their all being wounded soldiers would be.”
—National Woman’s Party, quoted in Everyone Was Brave. As, ch. 8, by William L. O’Neill (1969)
“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)