Classification of distributed binary labeling problems

DOI10.4230/LIPICS.DISC.2020.17MaRDI QIDQ6535014zbMATHFDO

Authors Alkida Balliu, Sebastian F. Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela

Publication date 2 November 2023

zbMATH Keywords

graph problemsLOCAL modeldistributed computational complexitylocally checkable labeling problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed systems (68M14)

Recommendations

• Brief Announcement: Classification of Distributed Binary Labeling Problems
• New classes of distributed time complexity
• Almost global problems in the LOCAL model
• Almost global problems in the LOCAL model
• Graph labelings derived from models in distributed computing: A complete complexity classification

Cites work

• scientific article; zbMATH DE number 6850477 (Why is no real title available?)
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
• A lower bound for the distributed Lovász local lemma
• A time hierarchy theorem for the LOCAL model
• Almost global problems in the LOCAL model
• An Automatic Speedup Theorem for Distributed Problems
• Brief Announcement: Classification of Distributed Binary Labeling Problems
• Brief Announcement: Round eliminator: a tool for automatic speedup simulation
• Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model
• Deterministic coin tossing with applications to optimal parallel list ranking
• Distributed Computing: A Locality-Sensitive Approach
• Distributed degree splitting, edge coloring, and orientations
• Hardness of Minimal Symmetry Breaking in Distributed Computing
• How much does randomness help with locally checkable problems?
• Improved distributed degree splitting and edge coloring
• LCL problems on grids
• Locality in Distributed Graph Algorithms
• New classes of distributed time complexity
• On the complexity of local distributed graph problems
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
• Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
• The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
• Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
• What Can be Computed Locally?

Cited in

(2)

• An efficient distributed algorithm for canonical labeling on directed split-stars
• Distributed Data Structures: A Survey on Informative Labeling Schemes

This page was built for publication: Classification of distributed binary labeling problems

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