In this chapter we show a general compact extended formulation for the relaxation of the stable set polytope. For some graphs the stable set polytope can be given an exact representation, although with an exponential number of inequalities. When the graphs are perfect, however, compact extended formulations are possible for the stable set polytope. We give an example of such situation by describing a compact extended formulation, obtained by LP techniques, for the class of comparability graphs.
Stable Sets
Lancia G.;Serafini P.
2018-01-01
Abstract
In this chapter we show a general compact extended formulation for the relaxation of the stable set polytope. For some graphs the stable set polytope can be given an exact representation, although with an exponential number of inequalities. When the graphs are perfect, however, compact extended formulations are possible for the stable set polytope. We give an example of such situation by describing a compact extended formulation, obtained by LP techniques, for the class of comparability graphs.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
