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)
“Friendship is learned by watching and listening to you. If she sees that your friends are people you like and trust and don’t pretend with—people who suit you—she probably won’t pick friends who just pass by, or people who can help her or improve her status. If you treat friends in a special way, if you are kinder, more generous, more sympathetic, more forgiving with friends, she probably will be, too.”
—Stella Chess (20th century)
“... and the next summer she died in childbirth.
That’s all. Of course, there may be some sort of sequel but it is not known to me. In such cases instead of getting bogged down in guesswork, I repeat the words of the merry king in my favorite fairy tale: Which arrow flies for ever? The arrow that has hit its mark.”
—Vladimir Nabokov (1899–1977)