Local conflict coloring revisited: Linial for lists

DOI10.4230/LIPICS.DISC.2020.16MaRDI QIDQ6535013zbMATH OpenFDO

Authors Yannic Maus, Tigran Tonoyan

Publication date 2 November 2023

zbMATH Keywords

list coloringdistributed graph coloringlow intersecting set families

Mathematics Subject Classification ID

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

Recommendations

• Linial for lists
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Distributed \(({\Delta}+1)\)-coloring in linear (in \({\Delta})\) time

Cites work

• scientific article; zbMATH DE number 4043100 (Why is no real title available?)
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• A lower bound for the distributed Lovász local lemma
• An Automatic Speedup Theorem for Distributed Problems
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• An optimal distributed \((\Delta+1)\)-coloring algorithm?
• Brief Announcement: Classification of Distributed Binary Labeling Problems
• Deterministic \((\Delta+1)\)-coloring in sublinear (in \(\Delta\)) time in static, dynamic, and faulty networks
• Deterministic distributed edge-coloring with fewer colors
• Deterministic distributed vertex coloring in polylogarithmic time
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Distributed degree splitting, edge coloring, and orientations
• Distributed deterministic edge coloring using bounded neighborhood independence
• Families of finite sets in which no set is covered by the union of \(r\) others
• Fast randomized algorithms for distributed edge coloring (extended abstract)
• Faster Deterministic Distributed Coloring Through Recursive List Coloring
• Improved distributed degree splitting and edge coloring
• Improved distributed delta-coloring
• Local computation: lower and upper bounds
• Locality based graph coloring
• Locality in Distributed Graph Algorithms
• Locality of not-so-weak coloring
• Locally-iterative distributed \((\Delta+1)\)-coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models
• On the complexity of distributed graph coloring
• On the complexity of distributed graph coloring with local minimality constraints
• On the complexity of local distributed graph problems
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Polynomial lower bound for distributed graph coloring in a weak LOCAL model
• Some simple distributed algorithms for sparse networks
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• The locality of distributed symmetry breaking
• Towards the locality of Vizing's theorem
• Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants

Cited in

(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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6535013)