Locally checkable problems in rooted trees

DOI10.1145/3465084.3467934MaRDI QIDQ6830481zbMATH OpenFDO

Authors Alkida Balliu, Sebastian F. Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, Aleksandr Tereshchenko

Publication date 26 March 2024

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

Full work available at URL https://doi.org/10.1145/3465084.3467934

zbMATH Keywords

distributed algorithmsrooted treeslocal modelCongest model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)

Cited in

(2)

• Completing the node-averaged complexity landscape of LCLs on trees
• Exponential speedup over locality in \textsf{MPC} with optimal memory

This page was built for publication: Locally checkable problems in rooted trees

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