Vis enkel innførsel

dc.contributor.authorGoyal, Prachi
dc.contributor.authorMisra, Pranabendu
dc.contributor.authorPanolan, Fahad
dc.contributor.authorPhilip, Geevarghese
dc.contributor.authorSaurabh, Saket
dc.date.accessioned2016-05-30T08:51:19Z
dc.date.available2016-05-30T08:51:19Z
dc.date.issued2015
dc.identifier.isbn978-3-939897-97-2
dc.identifier.issn1868-8969en_US
dc.identifier.urihttps://hdl.handle.net/1956/12030
dc.description.abstractProblems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on n vertices and a positive integer parameter k, find if there exist k edges(arcs) whose deletion results in a graph that satisfies some specified parity constraints. In particular, when the objective is to obtain a connected graph in which all the vertices have even degrees--where the resulting graph is Eulerian,the problem is called Undirected Eulerian Edge Deletion. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion. Cygan et al.[Algorithmica, 2014] showed that these problems are fixed parameter tractable (FPT), and gave algorithms with the running time 2^O(k log k)n^O(1). They also asked, as an open problem, whether there exist FPT algorithms which solve these problems in time 2^O(k)n^O(1). It was also posed as an open problem at the School on Parameterized Algorithms and Complexity 2014, Bedlewo, Poland. In this paper we answer their question in the affirmative: using the technique of computing representative families of co-graphic matroids we design algorithms which solve these problems in time 2^O(k)n^O(1). The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. We believe that this view-point/approach will be useful in other problems where one of the constraints that need to be satisfied is that of connectivity.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.subjectEulerian Edge Deletioneng
dc.subjectFPTeng
dc.subjectRepresentative Familyeng
dc.titleFinding even subgraphs even fasteren_US
dc.typePeer reviewed
dc.typeJournal article
dc.date.updated2016-03-30T10:15:41Z
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright Prachi Goyal, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, and Saket Saurabhen_US
dc.identifier.doihttps://doi.org/10.4230/lipics.fsttcs.2015.434
dc.identifier.cristin1344940
dc.source.journalLeibniz International Proceedings in Informatics
dc.source.pagenumber434-447
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400en_US
dc.identifier.citationLeibniz International Proceedings in Informatics 2015, 45:434-447
dc.source.volume45


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel

Attribution CC BY 3.0
Med mindre annet er angitt, så er denne innførselen lisensiert som Attribution CC BY 3.0