(2Δ — l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting
From MaRDI portal
Publication:5363083
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
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
