(2Δ — l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting

DOI10.1137/1.9781611973730.26zbMath1372.68210OpenAlexW4229705835MaRDI QIDQ5363083

Seth Pettie, Michael Elkin, Hsin-Hao Su

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.26

Mathematics Subject Classification ID

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

Related Items

On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Unnamed Item ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ Unnamed Item ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Distributed coloring algorithms for triangle-free graphs