imperfection ratio

The extreme points of QSTAB(G) and its implications

  • Arie M.C.A. Koster
  • Annegret K. Wagler
    • Categories 0-1 Programming, Graphs and Matroids, Polyhedra Tags , ,

    Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations w.r.t different concepts. Perfect graphs are, e.g., characterized as precisely those graphs G where the stable set polytope STAB(G) coincides with the clique constraint stable set polytope QSTAB(G). For all imperfect graphs STAB(G) \subset QSTAB(G) holds and, therefore, it is … Read more

    Comparing Imperfection Ratio and Imperfection Index for Graph Classes

  • Arie M.C.A. Koster
  • Annegret K. Wagler
    • Categories Graphs and Matroids, Polyhedra Tags , ,

    Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs $G$ where the stable set polytope $STAB(G)$ coincides with the fractional stable set polytope $QSTAB(G)$. For all imperfect graphs $G$ it holds that $STAB(G) \subset QSTAB(G)$. It … Read more