Distributed graph problems through an automata-theoretic Lens

DOI10.1007/978-3-030-79527-6_3OpenAlexW3128447208MaRDI QIDQ2117706FDOQ2117706

Authors: Yi-Jun Chang, Jan Studený, Jukka Suomela 

Publication date: 22 March 2022

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Cites Work

• Distributed Computing: A Locality-Sensitive Approach
• Title not available (Why is that?)
• Locality in Distributed Graph Algorithms
• Reset Sequences for Monotonic Automata
• Title not available (Why is that?)
• Distributed coloring algorithms for triangle-free graphs
• The locality of distributed symmetry breaking
• Deterministic coin tossing with applications to optimal parallel list ranking
• What Can be Computed Locally?
• Title not available (Why is that?)
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• A time hierarchy theorem for the LOCAL model
• Directable nondeterministic automata
• Improved upper bounds on synchronizing nondeterministic automata
• Synchronizing non-deterministic finite 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 degree splitting, edge coloring, and orientations
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• 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?
• Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
• Brief Announcement: Classification of Distributed Binary Labeling Problems
• The Distributed Complexity of Locally Checkable Problems on Paths is Decidable

Cited In (3)

• Extended dependency graphs and efficient distributed fixed-point computation
• Distributed graph problems through an automata-theoretic lens
• Local mending

This page was built for publication: Distributed graph problems through an automata-theoretic Lens

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