The Parameterized Hardness of the k-Center Problem in Transportation Networks
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10387192" target="_blank" >RIV/00216208:11320/18:10387192 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.SWAT.2018.19" target="_blank" >https://doi.org/10.4230/LIPIcs.SWAT.2018.19</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.SWAT.2018.19" target="_blank" >10.4230/LIPIcs.SWAT.2018.19</a>
Alternative languages
Result language
angličtina
Original language name
The Parameterized Hardness of the k-Center Problem in Transportation Networks
Original language description
In this paper we study the hardness of the k-Center problem on inputs that model transportation networks. For the problem, an edge-weighted graph G=(V,E) and an integer k are given and a center set C subseteq V needs to be chosen such that |C|<= k. The aim is to minimize the maximum distance of any vertex in the graph to the closest center. This problem arises in many applications of logistics, and thus it is natural to consider inputs that model transportation networks. Such inputs are often assumed to be planar graphs, low doubling metrics, or bounded highway dimension graphs. For each of these models, parameterized approximation algorithms have been shown to exist. We complement these results by proving that the k-Center problem is W[1]-hard on planar graphs of constant doubling dimension, where the parameter is the combination of the number of centers k, the highway dimension h, and even the treewidth t.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
ISBN
978-3-95977-068-2
ISSN
1868-8969
e-ISSN
neuvedeno
Number of pages
13
Pages from-to
1-13
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl, Germany
Event location
Malmö, Švédsko
Event date
Jun 18, 2018
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—