Show simple item record

Parameterized Dynamic Variants of Red-Blue Dominating Set

dc.contributor.authorAbu-Khzam, Faisal
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBazgan, Cristina
dc.contributor.authorFernau, Henning
dc.date.accessioned2021-11-26T13:41:18Z
dc.date.available2021-11-26T13:41:18Z
dc.date.issued2020
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22263
dc.language.isoenen
dc.subjectDynamic problemsen
dc.subjectReoptimizationen
dc.subjectParameterized complexityen
dc.subjectSet coveren
dc.subjectHitting seten
dc.subject.ddc004en
dc.titleParameterized Dynamic Variants of Red-Blue Dominating Seten
dc.typeCommunication / Conférence
dc.description.abstractenWe introduce a parameterized dynamic version of the Red-Blue Dominating Set problem and its partial version. We prove the fixed-parameter tractability of the dynamic versions with respect to the (so called) edit-parameter while they remain W[2] -hard with respect to the increment-parameter. We provide a complete study of the complexity of the problem with respect to combinations of the various parameters.en
dc.identifier.citationpages236-247en
dc.relation.ispartoftitleSOFSEM 2020: Theory and Practice of Computer Scienceen
dc.relation.ispartofeditorChatzigeorgiou, Alexander
dc.relation.ispartofeditorDondi, Riccardo
dc.relation.ispartofeditorHerodotou, Herodotos
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofdate2020
dc.relation.ispartofpages723en
dc.relation.ispartofurl10.1007/978-3-030-38919-2en
dc.subject.ddclabelInformatique généraleen
dc.relation.ispartofisbn978-3-030-38918-5en
dc.relation.conftitle46th International Conference on Current Trends in Theory and Practice of Informaticsen
dc.relation.confdate2020-01
dc.relation.confcityLimassolen
dc.relation.confcountryCyprusen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-030-38919-2_20en
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2021-11-26T13:34:49Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
Parameterized_Dynamic_Variants.pdf
Size:
303.5Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record