Referenz
Schneider, J., & Wattenhofer, R. (2010). A New Technique For Distributed Symmetry Breaking. Paper presented at the Principles of Distributed Computing (PODC).
Publikationsart
Beitrag in Konferenztagungsband
Abstract
We introduce Multi-Trials, a new technique for symmetry breaking for distributed algorithms and apply it to various problems in general graphs. For instance, we present three randomized algorithms for distributed (vertex or edge) coloring improving on previous algorithms and showing a time/color trade-off. To get a Delta + 1 coloring takes time O(log Delta + sqrt(log n)). To obtain an O(Delta + log1+1/ log* n n) coloring takes time O(log* n). This is more than an expo- nential improvement in time for graphs of polylogarithmic degree. Our fastest algorithm works in constant time using O(Delta log(c) n + log1+1/c n) colors, where c denotes an arbi- trary constant and log(c) n denotes the c times (recursively) applied logarithm to n. We also use the Multi-Trials technique to compute net- work decompositions and to compute maximal independent set (MIS), obtaining new results for several graph classes
Mitarbeiter
Einrichtungen
- Institut für Wirtschaftsinformatik
- Hilti Lehrstuhl für Business Process Management