Local conflict coloring revisited: Linial for lists

DOI10.4230/LIPICS.DISC.2020.16zbMATH Open1540.68308MaRDI QIDQ6535013FDOQ6535013

Authors: Yannic Maus, Tigran Tonoyan 

Publication date: 2 November 2023

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

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)

Cites Work

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

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)