Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma
From MaRDI portal
Publication:4973056
DOI10.1145/3365004zbMath1454.68167WikidataQ124978276 ScholiaQ124978276MaRDI QIDQ4973056
Wenzheng Li, Seth Pettie, Jara Uitto, Qizheng He, Yi-Jun Chang
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
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
Related Items
Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering, Distributed Lower Bounds for Ruling Sets, Component stability in low-space massively parallel computation, Distributed coloring of hypergraphs, Almost global problems in the LOCAL model