Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma

DOI10.1145/3365004zbMath1454.68167WikidataQ124978276 ScholiaQ124978276MaRDI QIDQ4973056

Jara Uitto, Yi-Jun Chang, Seth Pettie, Qizheng He, Wenzheng Li

Publication date: 2 December 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3365004

zbMATH Keywords

edge coloring; distributed algorithms; Lovász local lemma; LOCAL model

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

60C05: Combinatorial probability

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

68W20: Randomized algorithms

68W15: Distributed algorithms