Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems

DOI10.1145/3382734.3405721MaRDI QIDQ5855211zbMATH OpenOpenAlexFDO

Authors Will Rosenbaum, Jukka Suomela

Publication date 15 March 2021

Published in Proceedings of the 39th Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.08160

zbMATH Keywords

hierarchyLCLLOCAL modellocally checkable labelingquery complexityvolume complexity

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Cited in

(7)

• Introduction to local certification
• Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
• Improved dynamic colouring of sparse graphs
• Classification of distributed binary labeling problems
• The distributed complexity of locally checkable labeling problems beyond paths and trees
• Adaptive massively parallel coloring in sparse graphs
• Locally computing edge orientations

This page was built for publication: Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5855211)