1 citations · 1 across the 3 of their papers we have counts for
8 papers
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…
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…
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…
Two Player Hidden Pointer Chasing and Multi-Pass Lower Bounds in Turnstile Streams
Anay Mehrotra, Vibhor Porwal, Raghunath Tewari
The authors have withdrawn this paper due to an error in the proof of Lemma 3.4. -------------------------------------------------------------------------------------------- The au…
Reachability in High Treewidth Graphs
Rahul Jain, Raghunath Tewari
Reachability is the problem of deciding whether there is a path from one vertex to the other in the graph. Standard graph traversal algorithms such as DFS and BFS take linear time…
Circuit Complexity of Bounded Planar Cutwidth Graph Matching
Aayush Ojha, Raghunath Tewari
Recently, perfect matching in bounded planar cutwidth bipartite graphs (\BGGM) was shown to be in ACC by Hansen et al.. They also conjectured that the problem is in AC. In…