Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Competitive Random-Order Correlation k-Clustering
Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman +2
Correlation clustering has been extensively studied over the last two decades in many different computational models owing to its wide-ranging practical applications. The goal is t…
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…