Show simple item record

Independent Set Reconfiguration Parameterized by Modular-Width

hal.structure.identifierautre
dc.contributor.authorBelmonte, Rémy
hal.structure.identifier
dc.contributor.authorHanaka, Tesshu
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.identifierDepartment of Mathematical Informatics
dc.contributor.authorOno, Hirotaka
hal.structure.identifierKumamoto Gakuen University
dc.contributor.authorOtachi, Yota
dc.date.accessioned2019-12-16T15:46:26Z
dc.date.available2019-12-16T15:46:26Z
dc.date.issued2019
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20331
dc.language.isoenen
dc.subjectReconfigurationen
dc.subjectIndependent seten
dc.subjectModular-widthen
dc.subject.ddc511en
dc.titleIndependent Set Reconfiguration Parameterized by Modular-Widthen
dc.typeCommunication / Conférence
dc.description.abstractenIndependent Set Reconfiguration is one of the most well-studied problems in the setting of combinatorial reconfiguration. It is known that the problem is PSPACE-complete even for graphs of bounded bandwidth. This fact rules out the tractability of parameterizations by most well-studied structural parameters as most of them generalize bandwidth. In this paper, we study the parameterization by modular-width, which is not comparable with bandwidth. We show that the problem parameterized by modular-width is fixed-parameter tractable under all previously studied rules TAR, TJ, and TS. The result under TAR resolves an open problem posed by Bonsma [WG 2014, JGT 2016].en
dc.identifier.citationpages285-297en
dc.relation.ispartoftitleGraph-Theoretic Concepts in Computer Science, Revised Papersen
dc.relation.ispartofeditorSau, Ignasi
dc.relation.ispartofeditorThilikos, Dimitrios M.
dc.relation.ispartofpublnameSpringer International Publishingen
dc.relation.ispartofpublcityBerlin Heidelbergen
dc.relation.ispartofdate2019
dc.relation.ispartofpages394en
dc.relation.ispartofurl10.1007/978-3-030-30786-8en
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.ispartofisbn978-3-030-30785-1;978-3-030-30786-8en
dc.relation.conftitle45th International Workshop on Graph-Theoretic Concepts in Computer Scienceen
dc.relation.confdate2019-06
dc.relation.confcityVall de Núriaen
dc.relation.confcountrySpainen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-030-30786-8_22en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-12-16T15:39:39Z
hal.identifierhal-02414613*
hal.version1*
hal.update.actionupdateFiles*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
1905.00340.pdf
Size:
452.7Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record