We address the Max Cut problem by developing a compact formulation from the model expressing the condition that cuts and circuits have even intersection. This formulation turns out to be effective on sparse graphs especially with respect to the model based on triples of nodes.

An effective compact formulation of the max cut problem on sparse graphs

LANCIA, Giuseppe;SERAFINI, Paolo
2011

Abstract

We address the Max Cut problem by developing a compact formulation from the model expressing the condition that cuts and circuits have even intersection. This formulation turns out to be effective on sparse graphs especially with respect to the model based on triples of nodes.
File in questo prodotto:
File Dimensione Formato  
ENDM1223.pdf

non disponibili

Tipologia: Altro materiale allegato
Licenza: Non pubblico
Dimensione 337.65 kB
Formato Adobe PDF
337.65 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: http://hdl.handle.net/11390/881622
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact