Distributed graph problems through an automata-theoretic Lens
From MaRDI portal
Publication:2117706
DOI10.1007/978-3-030-79527-6_3OpenAlexW3128447208MaRDI QIDQ2117706
Jukka Suomela, Yi-Jun Chang, Jan Studený
Publication date: 22 March 2022
Full work available at URL: https://arxiv.org/abs/2002.07659
Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)
Related Items (3)
Locally checkable problems in rooted trees ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Local mending
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved upper bounds on synchronizing nondeterministic automata
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- Almost global problems in the LOCAL model
- Distributed coloring algorithms for triangle-free graphs
- The Locality of Distributed Symmetry Breaking
- Reset Sequences for Monotonic Automata
- Deterministic coin tossing with applications to optimal parallel list ranking
- Locality in Distributed Graph Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- Distributed Degree Splitting, Edge Coloring, and Orientations
- An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
- Synchronizing non-deterministic finite automata
- A Time Hierarchy Theorem for the LOCAL Model
- What Can be Computed Locally?
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
- 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
This page was built for publication: Distributed graph problems through an automata-theoretic Lens
