On the Complexity of Distributed Splitting Problems

DOI10.1145/3293611.3331630OpenAlexW3100926945MaRDI QIDQ5145221FDOQ5145221

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

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

zbMATH Keywords

randomnessdistributed graph algorithmslocal modelweak splittingdistributed symmetry breaking

Mathematics Subject Classification ID

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

Cited In (8)

• A combinatorial characterization of the distributed 1-solvable tasks
• On the distributed complexity of the semi-matching problem
• New classes of distributed time complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• An efficient distributed algorithm for canonical labeling on directed split-stars
• Title not available (Why is that?)
• 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)