Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim
Over the years, there has been extensive work on fully dynamic algorithms for classic graph problems that admit greedy solutions. Examples include vertex coloring, maximal…
cs.DS2024
Competitive Capacitated Online Recoloring
Rajmohan Rajaraman, Omer Wasim
In this paper, we revisit the online recoloring problem introduced recently by Azar et al. In online recoloring, there is a fixed set of vertices and an initial coloring $c…