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

Voir/Ouvrir
Type
Article accepté pour publication ou publié
Date
2019
Nom de la revue
Discrete Applied Mathematics
Volume
264
Éditeur
Elsevier
Pages
90-117
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(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]
Résumé (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.
Mots-clés
Clique-width; Treewidth; Domination