Classification of distributed binary labeling problems

DOI10.4230/LIPICS.DISC.2020.17zbMATH Open1540.68164MaRDI QIDQ6535014FDOQ6535014

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

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)

Cites Work

• Distributed Computing: A Locality-Sensitive Approach
• Locality in Distributed Graph Algorithms
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Deterministic coin tossing with applications to optimal parallel list ranking
• What Can be Computed Locally?
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• A Time Hierarchy Theorem for the LOCAL Model
• Title not available (Why is that?)
• Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
• Brief Announcement
• Distributed Degree Splitting, Edge Coloring, and Orientations
• On the complexity of local distributed graph 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?
• Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
• An Automatic Speedup Theorem for Distributed Problems
• Brief Announcement: Classification of Distributed Binary Labeling Problems
• The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
• Improved distributed degree splitting and edge coloring
• Almost global problems in the LOCAL model
• A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
• Hardness of Minimal Symmetry Breaking in Distributed Computing
• Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
• Brief Announcement: Round eliminator: a tool for automatic speedup simulation

Cited In (2)

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

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)