On rank-perfect subclasses of near-bipartite graphs |
| |
Authors: | Annegret K Wagler |
| |
Institution: | (1) Otto-von Guericke-University Magdeburg, Faculty for Mathematics, Institute for MathematicalOptimization (IMO), 39106 Magdeburg, Germany |
| |
Abstract: | Shepherd95 proved that the stable set polytopes of near-bipartite graphs are given by constraints associated with the complete
join of antiwebs only. For antiwebs, the facet set reduces to rank constraints associated with single antiwebs by Wagler2004.
We extend this result to a larger graph class, the complements of fuzzy circular interval graphs, recently introduced in ChudnovskySeymour2004.
Received: November 2004 / Revised version: June 2005 |
| |
Keywords: | Stable set polytope rank constraints antiwebs |
本文献已被 SpringerLink 等数据库收录! |
|