Improved approximation of Maximum Vertex Cover (Articolo in rivista)

Type
Label
  • Improved approximation of Maximum Vertex Cover (Articolo in rivista) (literal)
Anno
  • 2006-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1016/j.orl.2005.03.006 (literal)
Alternative label
  • Galluccio, A.; Nobili, P. (2006)
    Improved approximation of Maximum Vertex Cover
    in Operations research letters
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Galluccio, A.; Nobili, P. (literal)
Pagina inizio
  • 77 (literal)
Pagina fine
  • 84 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 34 (literal)
Rivista
Note
  • ISI Web of Science (WOS) (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Istituto analisi dei sistemi ed informatica \"Antonio Ruberti\" (literal)
Titolo
  • Improved approximation of Maximum Vertex Cover (literal)
Abstract
  • We provide a new LP relaxation of the maximum vertex cover problem and a polynomial-time algorithm that finds a solution within the approximation factor 1-1/(2\bar q), where \bar q is the size of the smallest clique in a given clique-partition of the edge weighting of G. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


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