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)
“The rebellion is against time pollution, the feeling that the essence of what makes life worth living—the small moments, the special family getaways, the cookies in the oven, the weekend drives, the long dreamlike summers Mso much of this has been taken from us, or we have given it up. For what? Hitachi stereos? Club Med? Company cars? Racquetball? For fifteen-hour days and lousy day care?”
—Richard Louv (20th century)
“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)