Show simple item record

dc.contributor.authorFomin, Fedor
dc.contributor.authorLokshtanov, Daniel
dc.contributor.authorRaman, Venkatesh
dc.contributor.authorSaurabh, Saket
dc.date.accessioned2016-05-30T09:29:17Z
dc.date.available2016-05-30T09:29:17Z
dc.date.issued2009
dc.PublishedLeibniz International Proceedings in Informatics 2009, 4:193-201eng
dc.identifier.urihttps://hdl.handle.net/1956/12033
dc.description.abstractPartial Cover problems are optimization versions of fundamental and well studied problems like {\sc Vertex Cover} and {\sc Dominating Set}. Here one is interested in covering (or dominating) the maximum number of edges (or vertices) using a given number \(k\) of vertices, rather than covering all edges (or vertices). In general graphs, these problems are hard for parameterized complexity classes when parameterized by \(k\). It was recently shown by Amini et. al. [{\em FSTTCS 08}\,] that {\sc Partial Vertex Cover} and {\sc Partial Dominating Set} are fixed parameter tractable on large classes of sparse graphs, namely \(H\).minor free graphs, which include planar graphs and graphs of bounded genus. In particular, it was shown that on planar graphs both problems can be solved in time \(2^{\cO(k)}n^{\cO(1)}\).en_US
dc.language.isoengeng
dc.publisherDagstuhl Publishingen_US
dc.rightsAttribution CC BY-NC-ND 3.0eng
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/eng
dc.subjectPartial cover problemseng
dc.subjectParameterized complexityeng
dc.subjectsubexponential time algorithmseng
dc.subjectirrelevant vertex techniqueeng
dc.titleSubexponential Algorithms for Partial Cover Problemsen_US
dc.typeConference object
dc.typePeer reviewed
dc.typeJournal article
dc.date.updated2016-04-07T06:45:15Z
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright Fomin, Lokshtanov, Raman and Saurabhen_US
dc.identifier.doihttps://doi.org/10.4230/lipics.fsttcs.2009.2318
dc.identifier.cristin343061
dc.subject.nsiVDP::Matematikk og naturvitenskap: 400::Matematikk: 410
dc.subject.nsiVDP::Mathematics and natural scienses: 400::Mathematics: 410
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Attribution CC BY-NC-ND 3.0
Except where otherwise noted, this item's license is described as Attribution CC BY-NC-ND 3.0