dc.contributor.author Bulian, Jannis en dc.contributor.author Dawar, Anuj en dc.date.accessioned 2017-01-05T14:12:29Z dc.date.available 2017-01-05T14:12:29Z dc.date.issued 2017-09-01 en dc.identifier.issn 0178-4617 dc.identifier.uri https://www.repository.cam.ac.uk/handle/1810/261747 dc.description.abstract We show that for various classes $\mathcal{C}$ of sparse graphs, and several measures of distance to such classes (such as edit distance and elimination distance), the problem of determining the distance of a given graph $\small{G}$ to $\mathcal{C}$ is fixed-parameter tractable. The results are based on two general techniques. The first of these, building on recent work of Grohe et al. establishes that any class of graphs that is slicewise nowhere dense and slicewise first-order definable is FPT. The second shows that determining the elimination distance of a graph $\small{G}$ to a minor-closed class $\mathcal{C}$ is FPT. We demonstrate that several prior results (of Golovach, Moser and Thilikos and Mathieson) on the fixed-parameter tractability of distance measures are special cases of our first method. dc.language English en dc.language.iso en en dc.publisher Springer dc.title Fixed-Parameter Tractable Distances to Sparse Graph Classes en dc.type Article prism.endingPage 158 prism.publicationDate 2017 en prism.publicationName Algorithmica en prism.startingPage 139 prism.volume 79 en dc.identifier.doi 10.17863/CAM.6963 dcterms.dateAccepted 2016-10-17 en rioxxterms.versionofrecord 10.1007/s00453-016-0235-7 en rioxxterms.version AM en rioxxterms.licenseref.uri http://www.rioxx.net/licenses/all-rights-reserved en rioxxterms.licenseref.startdate 2017-09-01 en dc.contributor.orcid Dawar, Anuj [0000-0003-4014-8248] dc.identifier.eissn 1432-0541 rioxxterms.type Journal Article/Review en cam.orpheus.success Thu Jan 30 12:53:29 GMT 2020 - The item has an open VoR version. * rioxxterms.freetoread.startdate 2100-01-01
﻿