6 papers
Parameterized Complexity of Maximum Edge Colorable Subgraph
Akanksha Agrawal, Madhumita Kundu, Abhishek Sahu +2
A graph is {\em -edge colorable} if there is a coloring , such that for distinct , we have . The {\sc…
The Parameterized Complexity of Guarding Almost Convex Polygons
Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov +2
Art Gallery is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an int…
FPT Algorithms for Conflict-free Coloring of Graphs and Chromatic Terrain Guarding
Akanksha Agrawal, Pradeesha Ashok, Meghana M Reddy +2
We present fixed parameter tractable algorithms for the conflict-free coloring problem on graphs. Given a graph , \emph{conflict-free coloring} of refers to coloring a…
On the Parameterized Complexity of Contraction to Generalization of Trees
Akanksha Agrawal, Saket Saurabh, Prafullkumar Tale
For a family of graphs , the -Contraction problem takes as an input a graph and an integer , and the goal is to decide if there exists $S \subseteq E(G)…
Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra +2
Given a graph and a parameter , the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset of size at most that hits all induced cycl…
Polylogarithmic Approximation Algorithms for Weighted--Deletion Problems
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra +2
For a family of graphs , the canonical Weighted Vertex Deletion problem is defined as follows: given an -vertex undirected graph and a weight function $w: V…