Showing cs.LOShow all
2 papers · 1 filter
cs.LO2026
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…
cs.LO2024
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…