15 papers · 1 filter
Connectivity Augmentation of Plane Graphs
Krishnan Dehaleesan, Asif Khan, Pranabendu Misra
We study the problem of connectivity augmentation of a planar graph, while preserving planarity. This problem is motivated by many real-world settings such as road-networks, power-…
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…
Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and Feedback Vertex Set
Sheikh Shakil Akhtar, Jayakrishnan Madathil, Pranabendu Misra +1
A typical goal of research in combinatorial optimization is to come up with fast algorithms that find optimal solutions to a computational problem. The process that takes a real-wo…
A Single Exponential-Time FPT Algorithm for Cactus Contraction
R. Krithika, Pranabendu Misra, Prafullkumar Tale
For a collection of graphs, the -\textsc{Contraction} problem takes a graph and an integer as input and decides if can be modified to some gr…
Robust Contraction Decomposition for Minor-Free Graphs and its Applications
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +6
We prove a robust contraction decomposition theorem for -minor-free graphs, which states that given an -minor-free graph and an integer , one can partition in polynomi…
Kernelization of Counting Problems
Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh +1
We introduce a new framework for the analysis of preprocessing routines for parameterized counting problems. Existing frameworks that encapsulate parameterized counting problems pe…