Name
Abstract | ||
|---|---|---|
Given a graph G = (V, E), a set of vertices S subset of V covers a vertex v is an element of V if the edge-connectivity between S and v is at least a given number k. Vertices in S are called sources. The maximum-cover source location problem, which is a variation of the source location problem, is to find a source set S with a given size at most p, maximizing the sum of the weight of vertices covered by S. In this paper, we show a polynomial-time algorithm for this problem in the case of k = 3 for a given undirected graph with a vertex weight function and an edge capacity function. Moreover, we show that this problem is NP-hard even if vertex weights and edge capacities are both uniform for general k. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/s00186-008-0266-1 | MATHEMATICAL METHODS OF OPERATIONS RESEARCH |
Keywords | Field | DocType |
Maximum-cover source location problem,Polynomial-time algorithm,NP-hard | Graph,Discrete mathematics,Mathematical optimization,Combinatorics,Weight function,Vertex (geometry),Vertex (graph theory),Edge cover,Neighbourhood (graph theory),Vertex cover,Feedback vertex set,Mathematics | Journal |
Volume | Issue | ISSN |
70.0 | 1.0 | 1432-2994 |
Citations | PageRank | References |
1 | 0.36 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kenya Sugihara | 1 | 9 | 3.00 |
| Hiro Ito | 2 | 290 | 39.95 |