Show simple item record

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

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKatsikarelis, Ioannis*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLampis, Michael
HAL ID: 182546
ORCID: 0000-0002-5791-0887		*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPaschos, Vangelis*
dc.date.accessioned2019-12-18T11:02:55Z
dc.date.available2019-12-18T11:02:55Z
dc.date.issued2019
dc.identifier.issn0166-218X
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20338
dc.language.isoenen
dc.subjectClique-widthen
dc.subjectTreewidthen
dc.subjectDominationen
dc.subject.ddc511en
dc.titleStructural parameters, tight bounds, and approximation for (k,r)-centeren
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn (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.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol264en
dc.relation.isversionofjnldate2019-07
dc.relation.isversionofjnlpages90-117en
dc.relation.isversionofdoi10.1016/j.dam.2018.11.002en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-12-16T15:55:30Z
hal.identifierhal-02417608*
hal.version1*
hal.update.actionupdateFiles*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
1704.08868.pdf
Size:
824.2Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record