Referenz
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).
Publikationsart
Beitrag in Konferenztagungsband
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.
Mitarbeiter
Einrichtungen
- Institut für Wirtschaftsinformatik
- Hilti Lehrstuhl für Business Process Management