4 papers
The Parameterized Complexity of Vertex-Coloring Edge-Weighting
Shubhada Aute, Fahad Panolan, Geevarghese Philip
Motivated by the landmark resolution of the 1-2-3 Conjecture, we initiate the study of the parameterized complexity of the Vertex-Coloring {0,1}-Edge-Weighting problem and its gene…
Exact Algorithms for Edge Deletion to Cactus
Sheikh Shakil Akhtar, Geevarghese Philip
We study two related problems on simple, un-directed graphs: Edge Deletion to Cactus and Spanning Tree to Cactus. Edge Deletion to Cactus has been known to be NP-hard on general gr…
Space Efficient Algorithms for Parameterised Problems
Sheikh Shakil Akhtar, Pranabendu Misra, Geevarghese Philip
We study "space efficient" FPT algorithms for graph problems with limited memory. Let n be the size of the input graph and k be the parameter. We present algorithms that run in tim…
Faster Algorithms for Graph Monopolarity
Geevarghese Philip, Shrinidhi Teganahally Sridhara
A graph is if its vertex set admits a partition where is a and is an $\textit{independent…