On the Complexity of Distributed Splitting Problems

DOI10.1145/3293611.3331630MaRDI QIDQ5145221zbMATH OpenOpenAlexFDO

Authors Philipp Bamberger, Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, Jara Uitto

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/1905.11573

zbMATH Keywords

randomnessdistributed graph algorithmslocal modelweak splittingdistributed symmetry breaking

Mathematics Subject Classification ID

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

Recommendations

• Hardness of Minimal Symmetry Breaking in Distributed Computing
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model
• The locality of distributed symmetry breaking
• Distributed degree splitting, edge coloring, and orientations

Cited in

(8)

• scientific article; zbMATH DE number 1696745 (Why is no real title available?)
• scientific article; zbMATH DE number 4218375 (Why is no real title available?)
• scientific article; zbMATH DE number 954657 (Why is no real title available?)
• A combinatorial characterization of the distributed 1-solvable tasks
• On the distributed complexity of the semi-matching problem
• An efficient distributed algorithm for canonical labeling on directed split-stars
• New classes of distributed time complexity
• Models of smoothing in dynamic networks

This page was built for publication: On the Complexity of Distributed Splitting Problems

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