Hardness of Minimal Symmetry Breaking in Distributed Computing

DOI10.1145/3293611.3331605OpenAlexW2962773915WikidataQ130857401 ScholiaQ130857401MaRDI QIDQ5145237FDOQ5145237

Authors: Alkida Balliu, Juho Hirvonen, Dennis Olivetti, Jukka Suomela 

Publication date: 20 January 2021

Published in: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

Recommendations

• On the Complexity of Distributed Splitting Problems
• Locality of not-so-weak coloring
• Polynomial lower bound for distributed graph coloring in a weak LOCAL model
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• On the complexity of distributed graph coloring

zbMATH Keywords

graph algorithmslocal modeldistributed complexity theorylocally checkable labelings

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (4)

• The complexity landscape of distributed locally checkable problems on trees
• Classification of distributed binary labeling problems
• Distributed Lower Bounds for Ruling Sets
• Title not available (Why is that?)

This page was built for publication: Hardness of Minimal Symmetry Breaking in Distributed Computing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145237)