Thumbnail

Structural parameters, tight bounds, and approximation for (k,r)-center

Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis (2019), Structural parameters, tight bounds, and approximation for (k,r)-center, Discrete Applied Mathematics, 264, p. 90-117. 10.1016/j.dam.2018.11.002

View/Open
Type
Article accepté pour publication ou publié
Date
2019
Journal name
Discrete Applied Mathematics
Volume
264
Publisher
Elsevier
Pages
90-117
Publication identifier
Metadata
Show full item record
Author(s)
Katsikarelis, Ioannis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
In (k,r)-Center we are given a (possibly edge-weighted) graph and are asked to select at most k vertices (centers), so that all other vertices are at distance at most r from a center. In this paper we provide a number of tight fine-grained bounds on the complexity of this problem with respect to various standard graph parameters.
Subjects / Keywords
Clique-width; Treewidth; Domination