Dispersing Obnoxious Facilities on a Graph

Algorithmica, vol. 83, pp. 1734–1749

Abstract

Abstract We study a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition that any two facilities have at least distance $$\delta$$ δ from each other. We investigate the complexity of this problem in terms of the rational parameter $$\delta$$ δ . The problem is polynomially solvable, if the numerator of $$\delta$$ δ is 1 or 2, while all other cases turn out to be NP-hard.

Authors 4

1. Alexander Grigoriev

   Maastricht University

   Affiliation as printed

   Department of Quantitative Economics, Maastricht University, Maastricht, The Netherlands

   Dept. of Quantitative Economics, Maastricht University, Maastricht, The Netherlands#TAB#

2. Tim A. Hartmann Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen, Aachen, Germany

   Dept. of Computer Science, RWTH Aachen, Aachen, Germany#TAB#

3. Stefan Lendl

   Graz University of Technology

   Affiliation as printed

   Institute of Discrete Mathematics, TU Graz, Graz, Austria

4. Gerhard J. Woeginger corresponding Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen, Aachen, Germany

   Dept. of Computer Science, RWTH Aachen, Aachen, Germany#TAB#