Deterministic (+1)-coloring in sublinear (in ) time in static, dynamic, and faulty networks
DOI10.1145/2979675zbMATH Open1426.68290OpenAlexW2554518674MaRDI QIDQ3177822FDOQ3177822
Authors: Leonid Barenboim 
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2979675
Recommendations
- Deterministic \(({\delta} + 1)\)-coloring in sublinear (in \({\delta}\)) time in static, dynamic and faulty networks
- Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
- Deterministic distributed vertex coloring in polylogarithmic time
- Deterministic distributed vertex coloring in polylogarithmic time
- Distributed \(({\Delta}+1)\)-coloring in linear (in \({\Delta})\) time
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)
Cited In (12)
- Linial for lists
- Making local algorithms wait-free: the case of ring coloring
- Self-stabilizing \((\varDelta +1)\)-coloring in sublinear (in \(\varDelta\)) rounds via locally-iterative algorithms
- Resource efficient stabilization for local tasks despite unknown capacity links
- Distributed coloring of hypergraphs
- Almost global problems in the LOCAL model
- Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
- Improved dynamic colouring of sparse graphs
- What can be sampled locally?
- Local conflict coloring revisited: Linial for lists
- Almost global problems in the LOCAL model
- Local mending
This page was built for publication: Deterministic \((\Delta+1)\)-coloring in sublinear (in \(\Delta\)) time in static, dynamic, and faulty networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177822)
