19 citations · 35 across the 5 of their papers we have counts for
5 papers
On finding highly connected spanning subgraphs
Manu Basavaraju, Pranabendu Misra, M. S. Ramanujan +1
In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph and an integer for every pair of vertices . The objective is to c…
Backdoors to Tractable Valued CSP
Robert Ganian, M. S. Ramanujan, Stefan Szeider
We extend the notion of a strong backdoor from the CSP setting to the Valued CSP setting (VCSP, for short). This provides a means for augmenting a class of tractable VCSP instances…
Combining Treewidth and Backdoors for CSP
Robert Ganian, M. S. Ramanujan, Stefan Szeider
We show that CSP is fixed-parameter tractable when parameterized by the treewidth of a backdoor into any tractable CSP problem over a finite constraint language. This result combin…
A Linear Time Parameterized Algorithm for Directed Feedback Vertex Set
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph on vertices and edges, and an integer . The objective is to determine whether there…
Faster Parameterized Algorithms using Linear Programming
Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman +2
We investigate the parameterized complexity of Vertex Cover parameterized by the difference between the size of the optimal solution and the value of the linear programming (LP) re…