
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
2019Nom de la revue
Discrete Applied MathematicsVolume
264Éditeur
Elsevier
Pages
90-117
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(s)
Katsikarelis, IoannisLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael

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; DominationPublications associées
Affichage des éléments liés par titre et auteur.
-
Katsikarelis, Ioannis (2019-12-12) Thèse
-
Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis (2018) Communication / Conférence
-
Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis (2022) Article accepté pour publication ou publié
-
Bonnet, Édouard; Lampis, Michael; Paschos, Vangelis (2018) Article accepté pour publication ou publié
-
Fotakis, Dimitris; Lampis, Michael; Paschos, Vangelis (2016) Communication / Conférence