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:
“Nothing in the world can take the place of Persistence. Talent will not; nothing is more common than unsuccessful men with talent. Genius will not; unrewarded genius is almost a proverb. Education will not; the world is full of educated derelicts. Persistence and Determination alone are omnipotent. The slogan “Press On”, has solved and will always solve the problems of the human race.”
—Calvin Coolidge (1872–1933)
“If there is a special Hell for writers it would be in the forced contemplation of their own works, with all the misconceptions, the omissions, the failures that any finished work of art implies.”
—John Dos Passos (1896–1970)
“Medication alone is not to be relied on. In one half the cases medicine is not needed, or is worse than useless. Obedience to spiritual and physical laws—hygeine [sic] of the body, and hygeine of the spirit—is the surest warrant for health and happiness.”
—Harriot K. Hunt (1805–1875)