2 papers
cs.DS2026
Dynamic Dominating Set in Uniformly Sparse Graphs
Anton Bukov, Shay Solomon
In the dynamic {\em minimum dominating set (MDS)} problem, the goal is to efficiently maintain an approximate MDS in an -vertex graph with vertex costs in undergoing e…
cs.DS2024
Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in- Time Barrier
Anton Bukov, Shay Solomon, Tianyi Zhang
The dynamic set cover problem has been subject to extensive research since the pioneering works of [Bhattacharya et al, 2015] and [Gupta et al, 2017]. The input is a set system $(U…