Showing 2020Show all
2 papers · 1 filter
cs.CC2020
Dynamic Complexity of Expansion
Samir Datta, Anuj Tawari, Yadu Vasudev
Dynamic Complexity was introduced by Immerman and Patnaik \cite{PatnaikImmerman97} (see also \cite{DongST95}). It has seen a resurgence of interest in the recent past, see \cite{Da…
cs.LO2020
Dynamic complexity of Reachability: How many changes can we handle?
Samir Datta, Pankaj Kumar, Anish Mukherjee +3
In 2015, it was shown that reachability for arbitrary directed graphs can be updated by first-order formulas after inserting or deleting single edges. Later, in 2018, this was exte…