Linial for lists

DOI10.1007/s00446-022-00424-yOpenAlexW4280610780MaRDI QIDQ2104037

Tigran Tonoyan, Yannic Maus

Publication date: 9 December 2022

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-022-00424-y

zbMATH Keywords

list coloringcover-free familycolor reductiondeterministic distributed coloring

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (2)

Lower bound for constant-size local certification ⋮ Distributed coloring of hypergraphs

Cites Work

• Unnamed Item
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Families of finite sets in which no set is covered by the union of \(r\) others
• Polynomial lower bound for distributed graph coloring in a weak LOCAL model
• Improved distributed degree splitting and edge coloring
• Locality of not-so-weak coloring
• A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
• On the complexity of distributed graph coloring with local minimality constraints
• Local Computation
• The Locality of Distributed Symmetry Breaking
• Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Distributed (Δ +1)-Coloring in Sublogarithmic Rounds
• Distributed Degree Splitting, Edge Coloring, and Orientations
• An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
• On the complexity of local distributed graph problems
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• Some simple distributed algorithms for sparse networks
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• An Automatic Speedup Theorem for Distributed Problems
• Faster Deterministic Distributed Coloring Through Recursive List Coloring
• On the complexity of distributed graph coloring
• Improved Distributed Delta-Coloring
• Locally-Iterative Distributed (Δ+ 1)
• Towards the locality of Vizing’s theorem
• Deterministic distributed edge-coloring with fewer colors
• An optimal distributed (Δ+1)-coloring algorithm?
• Locality based graph coloring
• A lower bound for the distributed Lovász local lemma
• Deterministic Distributed Vertex Coloring in Polylogarithmic Time
• Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
• Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
• Efficient Deterministic Distributed Coloring with Small Bandwidth
• Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta
• Brief Announcement: Classification of Distributed Binary Labeling Problems
• Distributed Lower Bounds for Ruling Sets

This page was built for publication: Linial for lists