The Locality of Distributed Symmetry Breaking

zurück zur Übersicht


Barenboim, L., Elkin,M, Pettie, S., & Schneider, J. (2016). The Locality of Distributed Symmetry Breaking. Journal of the ACM (JACM). (ABDC_2016: C; ABDC_2019: C; ISI_2016: 1.855; ISI_2016_5year: 4.509; ISI_2018: 2.17; VHB_3: B)


Beitrag in wissenschaftlicher Fachzeitschrift


Symmetry-breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this article we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the randomized complexity of four fundamental symmetry-breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets.



  • Institut für Wirtschaftsinformatik
  • Hilti Lehrstuhl für Business Process Management

Open Repository URL