6 citations · 9 across the 8 of their papers we have counts for
10 papers · 1 filter
An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set
Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan
We study the CONNECTED η-TREEDEPTH DELETION problem where the input instance is an undireted graph G = (V, E) and an integer k. The objective is to decide if G has a set S \subsete…
On the Parameterized Complexity of Deletion to -free Strong Components
Rian Neogi, M. S. Ramanujan, Saket Saurabh +1
{\sc Directed Feedback Vertex Set (DFVS)} is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the s…
On the Constrained Least-cost Tour Problem
Patrick O'Hara, M. S. Ramanujan, Theodoros Damoulas
We introduce the Constrained Least-cost Tour (CLT) problem: given an undirected graph with weight and cost functions on the edges, minimise the total cost of a tour rooted at a sta…
On the Approximate Compressibility of Connected Vertex Cover
Diptapriyo Majumdar, M. S. Ramanujan, Saket Saurabh
The Connected Vertex Cover problem, where the goal is to compute a minimum set of vertices in a given graph which forms a vertex cover and induces a connected subgraph, is a fundam…
Alternative parameterizations of Metric Dimension
Gregory Gutin, M. S. Ramanujan, Felix Reidl +1
A set of vertices in a graph is called resolving if for any two distinct , there is such that , where ${\rm di…
Reducing CMSO Model Checking to Highly Connected Graphs
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh +1
Given a Counting Monadic Second Order (CMSO) sentence , the CMSO problem is defined as follows. The input to CMSO is a graph , and the objective is to determine whe…