5 papers
Dynamic Planar Graph Isomorphism is in DynFO
Samir Datta, Asif Khan, Felix Tschirbs +2
Consider two planar graphs which are subject to edge insertions and deletions. We show that whether the two graphs are isomorphic can be maintained with first-order logic formulas…
Fast exact algorithms via the Matrix Tree Theorem
V. Arvind, Srijan Chakraborty, Samir Datta +1
Fast exact algorithms are known for Hamiltonian paths in undirected and directed bipartite graphs through elegant though involved algorithms that are quite different from each othe…
Derandomizing Isolation In Catalytic Logspace
V. Arvind, Srijan Chakraborty, Samir Datta
A language is said to be in catalytic logspace if we can test membership using a deterministic logspace machine that has an additional read/write tape filled with arbitrary data wh…
Revisiting Tree Canonization using polynomials
V. Arvind, Samir Datta, Salman Faris +1
Graph Isomorphism (GI) is a fundamental algorithmic problem. Amongst graph classes for which the computational complexity of GI has been resolved, trees are arguably the most funda…
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…