3 citations · 6 across the 6 of their papers we have counts for
16 papers
Query maintenance under batch changes with small-depth circuits
Samir Datta, Asif Khan, Anish Mukherjee +3
Which dynamic queries can be maintained efficiently? For constant-size changes, it is known that constant-depth circuits or, equivalently, first-order updates suffice for maintaini…
Dynamic Planar Embedding is in DynFO
Samir Datta, Asif Khan, Anish Mukherjee
Planar Embedding is a drawing of a graph on the plane such that the edges do not intersect each other except at the vertices. We know that testing the planarity of a graph and comp…
Approximating Edit Distance in the Fully Dynamic Model
Tomasz Kociumaka, Anish Mukherjee, Barna Saha
The edit distance is a fundamental measure of sequence similarity, defined as the minimum number of character insertions, deletions, and substitutions needed to transform one strin…
Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary
Adam Karczmarz, Anish Mukherjee, Piotr Sankowski
We study reachability and shortest paths problems in dynamic directed graphs. Whereas algebraic dynamic data structures supporting edge updates and reachability/distance queries ha…
The Parameterized Complexity of the Survivable Network Design Problem
Andreas Emil Feldmann, Anish Mukherjee, Erik Jan van Leeuwen
For the well-known Survivable Network Design Problem (SNDP) we are given an undirected graph with edge costs, a set of terminal vertices, and an integer demand fo…
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…