Towards the locality of Vizing’s theorem

DOI10.1145/3313276.3316393zbMath1433.68309arXiv1901.00479OpenAlexW2963472820MaRDI QIDQ5212777

Hsin-Hao Su, Hoa T. Vu

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1901.00479

zbMATH Keywords

edge coloringrandomized algorithmsdistributed algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

A fast distributed algorithm for \((\Delta+1)\)-edge-coloring, On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition, Linial for lists