Algorithms On Perfect Graphs
In all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time (Grötschel, Lovász & Schrijver 1988). The algorithm for the general case involves the use of the ellipsoid method for linear programming, but more efficient combinatorial algorithms are known for many special cases.
For many years the complexity of recognizing Berge graphs and perfect graphs remained open. From the definition of Berge graphs, it follows immediately that their recognition is in co-NP (Lovász 1983). Finally, subsequent to the proof of the strong perfect graph theorem, a polynomial time algorithm was discovered by Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković.
Read more about this topic: Perfect Graph
Famous quotes containing the word perfect:
“Such is the never-failing beauty and accuracy of language, the most perfect art in the world; the chisel of a thousand years retouches it.”
—Henry David Thoreau (1817–1862)