3 papers
cs.LO2021
Dynamic Meta-theorems for Distance and Matching
Samir Datta, Chetan Gupta, Rahul Jain +3
Reachability, distance, and matching are some of the most fundamental graph problems that have been of particular interest in dynamic complexity theory in recent years [DKMSZ18, DM…
cs.CC2021
Reachability and Matching in Single Crossing Minor Free Graphs
Samir Datta, Chetan Gupta, Rahul Jain +3
We show that for each single crossing graph , a polynomially bounded weight function for all -minor free graphs can be constructed in Logspace such that it gives nonzero…
cs.CC2020
Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs
Chetan Gupta, Rahul Jain, Raghunath Tewari
A graph separator is a subset of vertices of a graph whose removal divides the graph into small components. Computing small graph separators for various classes of graphs is an imp…