Local conflict coloring revisited: Linial for lists

DOI10.4230/lipics.disc.2020.16zbMATH Open1540.68308MaRDI QIDQ6535013

Yannic Maus, Tigran Tonoyan

Publication date: 2 November 2023

zbMATH Keywords

list coloringdistributed graph coloringlow intersecting set families

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

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
• 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
• 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
• Fast randomized algorithms for distributed edge 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
• Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta
• Brief Announcement: Classification of Distributed Binary Labeling Problems
• Distributed deterministic edge coloring using bounded neighborhood independence

Related Items (1)

Self-stabilizing \((\varDelta +1)\)-coloring in sublinear (in \(\varDelta\)) rounds via locally-iterative algorithms

This page was built for publication: Local conflict coloring revisited: Linial for lists