The Taub Faculty of Computer Science Events and Talks

Our research focuses on the task of Batched Vertex Cover Reconfiguration, both in centralized and distributed systems. In this talk, I will present a centralized black-box compression scheme for reconfiguration schedules. Afterwards, I will introduce the concept of Small Separator Decomposition which can be used to compute schedules in distributed systems and show how to compute it on specific graph classes in the LOCAL model of distributed computing. Lastly, I will complement the distributed results with a lower bound that shows that such decompositions are somewhat necessary.