Locally checkable problems in rooted trees
From MaRDI portal
Publication:6096035
DOI10.1007/s00446-022-00435-9arXiv2102.09277MaRDI QIDQ6096035
Aleksandr Tereshchenko, Alkida Balliu, Yi-Jun Chang, Jukka Suomela, Dennis Olivetti, Jan Studený, Sebastian F. Brandt
Publication date: 11 September 2023
Published in: Distributed Computing, Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2102.09277
Cites Work
- Distributed graph problems through an automata-theoretic Lens
- Deterministic coin tossing with applications to optimal parallel list ranking
- A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
- Locality in Distributed Graph Algorithms
- An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
- A Time Hierarchy Theorem for the LOCAL Model
- What Can be Computed Locally?
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Lower Bounds for Maximal Matchings and Maximal Independent Sets
- Almost global problems in the LOCAL model
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
- Hardness of Minimal Symmetry Breaking in Distributed Computing
- An Automatic Speedup Theorem for Distributed Problems
- New classes of distributed time complexity
- A lower bound for the distributed Lovász local lemma
- LCL Problems on Grids
- How much does randomness help with locally checkable problems?
- Brief Announcement: Classification of Distributed Binary Labeling Problems
- Brief Announcement: Round eliminator: a tool for automatic speedup simulation
- Distributed algorithms for the Lovász local lemma and graph coloring
This page was built for publication: Locally checkable problems in rooted trees
