Show simple item record

dc.contributor.authorPhilip, Geevarghese*
dc.contributor.authorPaul, Christophe*
dc.contributor.authorKim, Eun Jung*
dc.date.accessioned2012-07-16T12:23:16Z
dc.date.available2012-07-16T12:23:16Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9754
dc.language.isoenen
dc.subjectVertex Coveren
dc.subjectFPT timeen
dc.subject.ddc511en
dc.titleA single-exponential FPT algorithm for the K4-minor cover problemen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherCNRS, LIRMM, Montpellier, France;France
dc.contributor.editoruniversityotherMPII, Saarbr ucken;Allemagne
dc.description.abstractenGiven an input graph G and an integer k, the parameterized K4 -minor cover problem asks whether there is a set S of at most k vertices whose deletion results in a K4 -minor-free graph, or equivalently in a graph of treewidth at most 2. This problem is inspired by two well-studied parameterized vertex deletion problems, Vertex Cover and Feedback Vertex Set , which can also be expressed as Treewidth- t Vertex Deletion problems: t = 0 for Vertex Cover and t = 1 for Feedback Vertex Set . While a single-exponential FPT algorithm has been known for a long time for Vertex Cover , such an algorithm for Feedback Vertex Set was devised comparatively recently. While it is known to be unlikely that Treewidth- t Vertex Deletion can be solved in time co ( k ) nO (1) , it was open whether the K4 -minor cover could be solved in single-exponential FPT time, i.e. in ck nO (1) time. This paper answers this question in the a rmative.en
dc.relation.isversionofjnlnameJournal of Computer and System Sciences
dc.relation.isversionofjnlvol81
dc.relation.isversionofjnlissue1
dc.relation.isversionofjnldate2015
dc.relation.isversionofjnlpages186-207
dc.relation.isversionofdoi10.1016/j.jcss.2014.05.001
dc.identifier.urlsitehttp://arxiv.org/abs/1204.1417v1
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.person.labIds*
hal.person.labIds*
hal.person.labIds989*
hal.identifierhal-01496435*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record