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:
“...I never drink wine ... I keep my hands soft and supple ... I sleep in a soft bed and never over-tire my body. It is because when my hour strikes I must be a perfect instrument. My eyes must be steady, my brain clear, my nerves calm, my aim true. I must be prepared to do my work, successfully if God wills. But if I perish, I perish.”
—Lisa, Russian terrorist (anonymous)