http://www.cnr.it/ontology/cnr/individuo/prodotto/ID291668
IMPROVED APPROXIMATION OF MAXIMUM VERTEX COVERAGE PROBLEM ON BIPARTITE GRAPHS (Articolo in rivista)
- Type
- Label
- IMPROVED APPROXIMATION OF MAXIMUM VERTEX COVERAGE PROBLEM ON BIPARTITE GRAPHS (Articolo in rivista) (literal)
- Anno
- 2014-01-01T00:00:00+01:00 (literal)
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
- 10.1137/130931059 (literal)
- Alternative label
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
- Apollonio, Nicola; Simeone, Bruno (literal)
- Pagina inizio
- Pagina fine
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
- Rivista
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroFascicolo
- Note
- ISI Web of Science (WOS) (literal)
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
- Consiglio Nazionale delle Ricerche (CNR); Sapienza University Rome (literal)
- Titolo
- IMPROVED APPROXIMATION OF MAXIMUM VERTEX COVERAGE PROBLEM ON BIPARTITE GRAPHS (literal)
- Abstract
- Given a simple undirected graph G and a positive integer s, the maximum vertex coverage problem (MVC) is the problem of finding a set U of s vertices of G such that the number of edges having at least one endpoint in U is as large as possible. The problem is NP-hard even in bipartite graphs, as shown in two recent papers [N. Apollonio and B. Simeone, Discrete Appl. Math., 165 (2014), pp. 37-48; G. Joret and A. Vetta, Reducing the Rank of a Matroid, preprint, arXiv: 1211.4853v1 [cs.DS], 2012]. By exploiting the structure of the fractional optimal solutions of a linear programming formulation for the maximum coverage problem, we provide a 4/5-approximation algorithm for the problem. The algorithm immediately extends to the weighted version of MVC. (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
