文章基本信息

标题：Dispersing Obnoxious Facilities on a Graph
本地全文：下载
作者：Alexander Grigoriev ; Tim A. Hartmann ; Stefan Lendl 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：126
页码：1-11
DOI：10.4230/LIPIcs.STACS.2019.33
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：algorithms; complexity; optimization; graph theory; facility location