Deterministic (+1)-coloring in sublinear (in ) time in static, dynamic, and faulty networks

DOI10.1145/2979675MaRDI QIDQ3177822zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

partitionsdistributed algorithmspolynomialscoloring

Mathematics Subject Classification ID

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)

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

Cited in

(19)

• Linial for lists
• Tight lower bounds in the supported LOCAL model
• Making local algorithms wait-free: the case of ring coloring
• Sublinear algorithms for ( + 1) vertex coloring
• Self-stabilizing ( +1)-coloring in sublinear (in ) rounds via locally-iterative algorithms
• Distributed fractional local ratio and independent set approximation
• Resource efficient stabilization for local tasks despite unknown capacity links
• Distributed (+1)-coloring via ultrafast graph shattering
• Distributed coloring of hypergraphs
• Graph coloring via degeneracy in streaming and other space-conscious models
• Deterministic \(({\delta} + 1)\)-coloring in sublinear (in \({\delta}\)) time in static, dynamic and faulty networks
• 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
• Locally-iterative (+1)-coloring in sublinear (in ) rounds
• 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)