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.

Authors :
Sugihara, Kenya
Ito, Hiro
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