Comparing Imperfection Ratio and Imperfection Index for Graph Classes

DOI10.1051/ro:2008030zbMath1197.05064OpenAlexW2111815194MaRDI QIDQ3163670

Arie M. C. A. Koster, Annegret K. Wagler

Publication date: 26 October 2010

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/105416

zbMATH Keywords

perfect graphsimperfection ratioimperfection index

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Perfect graphs (05C17)

Related Items

Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs ⋮ Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs ⋮ Unnamed Item ⋮ On determining the imperfection ratio

Cites Work

• The strong perfect graph theorem
• Characterizing and bounding the imperfection ratio for some classes of graphs
• Graphical properties related to minimal imperfection
• Geometric algorithms and combinatorial optimization
• Near-perfect matrices
• On certain polytopes associated with graphs
• Lift-and-project cuts and perfect graphs
• Graph imperfection. I
• Antiwebs are rank-perfect
• Lift-and-project ranks and antiblocker duality
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• On rank-perfect subclasses of near-bipartite graphs
• Normal hypergraphs and the perfect graph conjecture
• Polyhedra for Composed Independence Systems
• The fractional chromatic number of infinite graphs
• Maximum matching and a polyhedron with 0,1-vertices
• A Generalization of the Perfect Graph Theorem Under the Disjunctive Index
• Note On: N. E. Aguilera, M. S. Escalante, G. L. Nasini, “A Generalization of the Perfect Graph Theorem Under the Disjunctive Index”
• Sur le coloriage des graphs

This page was built for publication: Comparing Imperfection Ratio and Imperfection Index for Graph Classes