Show simple item record

dc.contributor.authorKolay, Sudeshna
dc.contributor.authorLokshtanov, Daniel
dc.contributor.authorPanolan, Fahad
dc.contributor.authorSaurabh, Saket
dc.date.accessioned2016-05-27T11:12:27Z
dc.date.available2016-05-27T11:12:27Z
dc.date.issued2015
dc.PublishedLeibniz International Proceedings in Informatics 2015, 43:258-269eng
dc.identifier.issn1868-8969en_US
dc.identifier.urihttps://hdl.handle.net/1956/12024
dc.description.abstractLet F be a family of graphs. Given an input graph G and a positive integer k, testing whether G has a k-sized subset of vertices S, such that G\S belongs to F, is a prototype vertex deletion problem. These type of problems have attracted a lot of attention in recent times in the domain of parameterized complexity. In this paper, we study two such problems; when F is either a family of cactus graphs or a family of odd-cactus graphs. A graph H is called a cactus graph if every pair of cycles in H intersect on at most one vertex. Furthermore, a cactus graph H is called an odd cactus, if every cycle of H is of odd length. Let us denote by C and C_{odd}, families of cactus and odd cactus, respectively. The vertex deletion problems corresponding to C and C_{odd} are called Diamond Hitting Set and Even Cycle Transversal, respectively. In this paper we design randomized algorithms with running time 12^{k}*n^{O(1)} for both these problems. Our algorithms considerably improve the running time for Diamond Hitting Set and Even Cycle Transversal, compared to what is known about them.en_US
dc.language.isoengeng
dc.publisherDagstuhl Publishingen_US
dc.rightsAttribution CC BY 3.0eng
dc.rights.urihttp://creativecommons.org/licenses/by/3.0eng
dc.subjectEven Cycle Transversaleng
dc.subjectDiamond Hitting Seteng
dc.subjectRandomized Algorithmseng
dc.titleQuick but odd growth of cactien_US
dc.typeConference object
dc.typePeer reviewed
dc.typeJournal article
dc.date.updated2016-03-30T09:45:28Z
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabhen_US
dc.identifier.doihttps://doi.org/10.4230/lipics.ipec.2015.258
dc.identifier.cristin1344962
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 3.0
Except where otherwise noted, this item's license is described as Attribution CC BY 3.0