Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Batched Vertex Cover Reconfiguration
event speaker icon
Shahar Romem Peled (M.Sc. Thesis Seminar)
event date icon
Thursday, 18.02.2021, 14:30
event location icon
Zoom Lecture: 99681314877
For password to lecture, please contact:
event speaker icon
Advisor: Prof. Kere. Censor-Hillel
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.