Show simple item record

dc.contributor.authorBulian, Jannisen
dc.contributor.authorDawar, Anujen
dc.date.accessioned2017-01-05T14:12:29Z
dc.date.available2017-01-05T14:12:29Z
dc.date.issued2017-09-01en
dc.identifier.issn0178-4617
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/261747
dc.description.abstractWe 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.languageEnglishen
dc.language.isoenen
dc.publisherSpringer
dc.titleFixed-Parameter Tractable Distances to Sparse Graph Classesen
dc.typeArticle
prism.endingPage158
prism.publicationDate2017en
prism.publicationNameAlgorithmicaen
prism.startingPage139
prism.volume79en
dc.identifier.doi10.17863/CAM.6963
dcterms.dateAccepted2016-10-17en
rioxxterms.versionofrecord10.1007/s00453-016-0235-7en
rioxxterms.versionAMen
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserveden
rioxxterms.licenseref.startdate2017-09-01en
dc.contributor.orcidDawar, Anuj [0000-0003-4014-8248]
dc.identifier.eissn1432-0541
rioxxterms.typeJournal Article/Reviewen
cam.orpheus.successThu Jan 30 12:53:29 GMT 2020 - The item has an open VoR version.*
rioxxterms.freetoread.startdate2100-01-01


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record