(2-1)-edge-coloring is much easier than maximal matching in the distributed setting
DOI10.1137/1.9781611973730.26zbMATH Open1372.68210OpenAlexW4229705835MaRDI QIDQ5363083FDOQ5363083
Authors: Michael Elkin, Seth Pettie, 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
Recommendations
- Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
- Deterministic distributed edge-coloring with fewer colors
- Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
- Nearly optimal distributed edge coloring in O(log log n) rounds
- Distributed edge coloring and a special case of the constructive Lovász local lemma
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15)
Cited In (21)
- Towards the locality of Vizing's theorem
- Deterministic distributed edge-coloring with fewer colors
- Improved distributed degree splitting and edge coloring
- Distributed edge coloring and a special case of the constructive Lovász local lemma
- A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
- Title not available (Why is that?)
- Distributed algorithms for the Lovász local lemma and graph coloring
- Distributed deterministic edge coloring using bounded neighborhood independence
- Distributed \((\Delta+1)\)-coloring via ultrafast graph shattering
- Distributed coloring and the local structure of unit-disk graphs
- Superfast coloring in CONGEST via efficient color sampling
- Superfast coloring in CONGEST via efficient color sampling
- Title not available (Why is that?)
- Improved distributed degree splitting and edge coloring
- Coloring fast without learning your neighbors' colors
- Distributed coloring algorithms for triangle-free graphs
- Some simple distributed algorithms for sparse networks
- Distributed degree splitting, edge coloring, and orientations
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- Locally-iterative distributed \((\Delta+1)\)-coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models
- Fast randomized algorithms for distributed edge coloring (extended abstract)
This page was built for publication: \((2\Delta-1)\)-edge-coloring is much easier than maximal matching in the distributed setting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363083)
