Vis enkel innførsel

dc.contributor.authorFomin, Fedor
dc.contributor.authorGolovach, Petr
dc.date.accessioned2022-01-31T13:42:24Z
dc.date.available2022-01-31T13:42:24Z
dc.date.created2022-01-06T10:38:02Z
dc.date.issued2021
dc.identifier.issn0895-4801
dc.identifier.urihttps://hdl.handle.net/11250/2976048
dc.description.abstractA fundamental theorem of Whitney from 1933 asserts that 2-connected graphs $G$ and $H$ are 2-isomorphic, or equivalently, their cycle matroids are isomorphic if and only if $G$ can be transformed into $H$ by a series of operations called Whitney switches. In this paper we consider the quantitative question arising from Whitney's theorem: Given two 2-isomorphic graphs, can we transform one into another by applying at most $k$ Whitney switches? This problem is already \sf NP-complete for cycles, and we investigate its parameterized complexity. We show that the problem admits a kernel of size $\mathcal{O}(k)$ and thus is fixed-parameter tractable when parameterized by $k$.en_US
dc.language.isoengen_US
dc.publisherSIAMen_US
dc.titleKernelization of Whitney Switchesen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright 2021 Society for Industrial and Applied Mathematicsen_US
cristin.ispublishedtrue
cristin.fulltextpreprint
cristin.qualitycode1
dc.identifier.doihttps://doi.org/10.1137/20M1367519
dc.identifier.cristin1975700
dc.source.journalSIAM Journal on Discrete Mathematicsen_US
dc.source.pagenumber1298-1336en_US
dc.relation.projectNorges forskningsråd: 263317en_US
dc.identifier.citationSIAM Journal on Discrete Mathematics. 2021, 35 (2), 1298-1336.en_US
dc.source.volume35en_US
dc.source.issue2en_US


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel