Show simple item record

dc.contributor.authorFomin, Fedor
dc.contributor.authorLokshtanov, Daniel
dc.contributor.authorRaman, Venkatesh
dc.contributor.authorSaurabh, Saket
dc.PublishedLeibniz International Proceedings in Informatics 2009, 4:193-201eng
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.publisherDagstuhl Publishingen_US
dc.rightsAttribution CC BY-NC-ND 3.0eng
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.rights.holderCopyright Fomin, Lokshtanov, Raman and Saurabhen_US
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


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