3 papers
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…
cs.GT2023
Sample Complexity of Linear Regression Models for Opinion Formation in Networks
Haolin Liu, Rajmohan Rajaraman, Ravi Sundaram +3
Consider public health officials aiming to spread awareness about a new vaccine in a community interconnected by a social network. How can they distribute information with minimal…