In this chapter we compare three popular models for the maximum cut problem and show the equivalence of their relaxations by using compact extended formulations. These problems are closely related to the subject of edge-induced and node-induced bipartite subgraphs, for which we give compact extended formulations as well.
Cuts and Induced Bipartite Subgraphs
Lancia G.;Serafini P.
2018-01-01
Abstract
In this chapter we compare three popular models for the maximum cut problem and show the equivalence of their relaxations by using compact extended formulations. These problems are closely related to the subject of edge-induced and node-induced bipartite subgraphs, for which we give compact extended formulations as well.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.
