| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418867 | Discrete Applied Mathematics | 2014 | 12 Pages |
Abstract
Given a simple undirected graph GG and a positive integer ss the Maximum Vertex Coverage Problem is the problem of finding a set UU of ss vertices of GG such that the number of edges having at least one endpoint in UU is as large as possible. We prove that the Maximum Vertex Coverage problem on bipartite graphs is NP-hard and discuss several consequences related to known combinatorial optimization problems.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Nicola Apollonio, Bruno Simeone,