Back to Search
Start Over
Maximum-cover source location problems with objective edge-connectivity three.
Maximum-cover source location problems with objective edge-connectivity three.
- Source :
- Mathematical Methods of Operations Research; Aug2009, Vol. 70 Issue 1, p183-193, 11p, 4 Diagrams
- Publication Year :
- 2009
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 14322994
- Volume :
- 70
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Mathematical Methods of Operations Research
- Publication Type :
- Academic Journal
- Accession number :
- 43468370
- Full Text :
- https://doi.org/10.1007/s00186-008-0266-1