Easy and Difficult Objective Functions for Max Cut (Articolo in rivista)

Type
Label
  • Easy and Difficult Objective Functions for Max Cut (Articolo in rivista) (literal)
Anno
  • 2003-01-01T00:00:00+01:00 (literal)
Alternative label
  • McCormick, S.T.; Rao, M.R.; Rinaldi, G. (2003)
    Easy and Difficult Objective Functions for Max Cut
    in Mathematical programming
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • McCormick, S.T.; Rao, M.R.; Rinaldi, G. (literal)
Pagina inizio
  • 459 (literal)
Pagina fine
  • 466 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 94 (literal)
Rivista
Note
  • ISI Web of Science (WOS) (literal)
Titolo
  • Easy and Difficult Objective Functions for Max Cut (literal)
Abstract
  • This note investigates the boundary between polynomially-solvable Max Cut and NP Hard Max Cut instances when they are classified only on the basis of the sign pattern of the objective function coefficients, i.e., of the orthant containing the objective function vector. It turns out that the matching number of the subgraph induced by the positive edges is the key parameter that allows us to differentiate between polynomially-solvable and hard instances of the problem. We give some applications of the polynomially solvable cases. (literal)
Prodotto di
Autore CNR

Incoming links:


Autore CNR di
Prodotto
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
data.CNR.it