Showing 2021Show all
2 papers · 1 filter
cs.DS2021
Locality in online, dynamic, sequential, and distributed graph algorithms
Amirreza Akbari, Navid Eslami, Henrik Lievonen +3
In this work, we give a unifying view of locality in four settings: distributed algorithms, sequential greedy algorithms, dynamic algorithms, and online algorithms. We introduce a…
cs.DC2021
Local Mending
Alkida Balliu, Juho Hirvonen, Darya Melnyk +3
In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far o…