Classification of distributed binary labeling problems

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

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) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14)

Cites Work

• Title not available (Why is that?)
• 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
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Degree Splitting, Edge Coloring, and Orientations
• A Time Hierarchy Theorem for the LOCAL Model
• What Can be Computed Locally?
• On the complexity of local distributed graph problems
• 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
• A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
• New classes of distributed time complexity
• A lower bound for the distributed Lovász local lemma
• Brief Announcement
• LCL Problems on Grids
• Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
• Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
• 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
• Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
• Improved distributed degree splitting and edge coloring

Related Items (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)