Name
Abstract | ||
|---|---|---|
Given a graph G = (V, E), a set of vertices $${S \subseteq V}$$ covers a vertex $${v \in 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 |
|---|---|---|
2009 | 10.1007/s00186-008-0266-1 | Math. Meth. of OR |
Keywords | Field | DocType |
maximum-cover source location problem · polynomial-time algorithm · np-hard,connected component | Dynamic programming,Mathematical optimization,Facility location problem,1-center problem,Mathematics | Journal |
Volume | Issue | ISSN |
70 | 1 | 1432-2994 |
Citations | PageRank | References |
1 | 0.36 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kenya Sugihara | 1 | 9 | 3.00 |
| Hiro Ito | 2 | 290 | 39.95 |