The distributed complexity of locally checkable labeling problems beyond paths and trees
From MaRDI portal
Cites work
- A lower bound for the distributed Lovász local lemma
- A meta-theorem for distributed certification
- A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
- A time hierarchy theorem for the LOCAL model
- Almost global problems in the LOCAL model
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- Classification of distributed binary labeling problems
- Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
- Distributed algorithms for the Lovász local lemma and graph coloring
- Distributed algorithms for weighted problems in sparse graphs
- Distributed Almost Exact Approximations for Minor-Closed Families
- Distributed approximation algorithms for k-dominating set in graphs of bounded genus and linklessly embeddable graphs
- Distributed Approximation Algorithms for Planar Graphs
- Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families
- Distributed coloring algorithms for triangle-free graphs
- Distributed Dominating Set Approximations beyond Planar Graphs
- Distributed graph problems through an automata-theoretic lens
- Distributed minimum dominating set approximations in restricted families of graphs
- Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
- Fast Distributed Approximations in Planar Graphs
- Faster distributed shortest path approximations via shortcuts
- Graph minors. I. Excluding a forest
- Graph minors. V. Excluding a planar graph
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XX: Wagner's conjecture
- How much does randomness help with locally checkable problems?
- scientific article; zbMATH DE number 4173000 (Why is no real title available?)
- scientific article; zbMATH DE number 7774264 (Why is no real title available?)
- scientific article; zbMATH DE number 7829261 (Why is no real title available?)
- Improved distributed algorithms for the Lovász local lemma and edge coloring
- Improved distributed delta-coloring
- LCL problems on grids
- Local Certification of Graph Decompositions and Applications to Minor-Free Classes
- Local certification of graphs with bounded genus
- Local conflict coloring
- Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
- Locality in Distributed Graph Algorithms
- Locality in online, dynamic, sequential, and distributed graph algorithms
- Locally checkable labelings with small messages
- Locally checkable problems in rooted trees
- Low-Congestion Shortcuts for Graphs Excluding Dense Minors
- Low-congestion shortcuts without embedding
- Minor excluded network families admit fast distributed algorithms
- Narrowing the LOCAL-CONGEST Gaps in Sparse Networks via Expander Decompositions
- Near-optimal distributed DFS in planar graphs
- Near-optimal low-congestion shortcuts on bounded parameter graphs
- New classes of distributed time complexity
- On derandomizing local distributed algorithms
- Optimal distributed coloring algorithms for planar graphs in the LOCAL model
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- Property testing of planarity in the \textsf{CONGEST} model
- Round- and message-optimal distributed graph algorithms
- Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
- Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
- Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
- The complexity landscape of distributed locally checkable problems on trees
- The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
- The disjoint paths problem in quadratic time
- The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
- The Landscape of Distributed Complexities on Trees and Beyond
- The locality of distributed symmetry breaking
- The Parallel Complexity of Tree Embedding Problems
- The power of distributed verifiers in interactive proofs
- The power of multi-step Vizing chains
- What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs
- What Can be Computed Locally?
This page was built for publication: The distributed complexity of locally checkable labeling problems beyond paths and trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6906410)
