Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874645 | Journal of Computer and System Sciences | 2018 | 13 Pages |
Abstract
In the Undirected Eulerian Edge Deletion problem, we are given an undirected graph and an integer k, and the objective is to delete k edges such that the resultant graph is a connected graph in which all the vertices have even degrees. 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. In this paper, using the technique of computing representative families of co-graphic matroids we design algorithms which solve these problems in time 2O(k)nO(1), improving the algorithms by Cygan et al. [Algorithmica, 2014] and affirmatively answer the open problem posed by them. The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Prachi Goyal, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, Saket Saurabh,