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:
“America is a great country. It has many shortcomings, many social inequalities, and it’s tragic that the problem of the blacks wasn’t solved fifty or even a hundred years ago, but it’s still a great country, a country full of opportunities, of freedom! Does it seem nothing to you to be able to say what you like, even against the government, the Establishment?”
—Golda Meir (1898–1978)
“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)
“In most cases a favorite writer is more with us in his book than he ever could have been in the flesh; since, being a writer, he is one who has studied and perfected this particular mode of personal incarnation, very likely to the detriment of any other. I should like as a matter of curiosity to see and hear for a moment the men whose works I admire; but I should hardly expect to find further intercourse particularly profitable.”
—Charles Horton Cooley (1864–1929)