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.
2018
978-3-319-63975-8
978-3-319-63976-5
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/1214348
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact