Reference
Barenboim, L., Elkin,M, Pettie, S., & Schneider, J. (2012). The Locality of Distributed Symmetry Breaking. Paper presented at the Symposium on Foundations of Computer Science (FOCS).
Publication type
Paper in Conference Proceedings
Abstract
We present new bounds on the locality of several classical symmetry breaking tasks in distributed networks. We also introduce a new technique for reducing symmetry breaking problems on low arboricity graphs to low degree graphs. Corollaries of this reduction include MM and MIS algorithms for low arboricity graphs (e.g., planar graphs and graphs that exclude any ?xed minor) requiring O(sqrt(log n)) and O(log^{2/3} n) rounds w.h.p., respectively.
Persons
Organizational Units
- Institute of Information Systems
- Hilti Chair of Business Process Management