期刊
MATHEMATICAL PROGRAMMING
卷 192, 期 1-2, 页码 207-227出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-021-01646-x
关键词
Covering; Location theory; Graph theory; Complexity; Parametrized complexity
类别
资金
- Austrian Science Fund (FWF): Doctoral Program Discrete Mathematics [W1230]
- DFG [RTG 2236]
The study focuses on a continuous facility location problem on undirected graphs, aiming to cover the entire graph with a minimum number of facilities. The problem is proven to be polynomially solvable when delta is a unit fraction. However, it becomes NP-hard for all non unit fractions delta. Moreover, the parametrized complexity is analyzed, showing that the problem is fixed parameter tractable for delta < 3/2 and W[2]-hard for delta >= 3/2.
We study a continuous facility location problem on undirected graphs where all edges have unit length and where the facilities may be positioned on the vertices as well as on interior points of the edges. The goal is to cover the entire graph with a minimum number of facilities with covering range delta > 0. In other words, we want to position as few facilities as possible subject to the condition that every point on every edge is at distance at most delta from one of these facilities. We investigate this covering problem in terms of the rational parameter delta. We prove that the problem is polynomially solvable whenever delta is a unit fraction, and that the problem is NP-hard for all non unit fractions delta. We also analyze the parametrized complexity with the solution size as parameter: The resulting problem is fixed parameter tractable for delta < 3/2, and it is W[2]-hard for delta >= 3/2.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据