Symmetry Breaking Depending on the Chromatic Number or the Neighborhood Growth

zurück zur Übersicht


Schneider, J., Elkin, M., & Wattenhofer, R. (2012). Symmetry Breaking Depending on the Chromatic Number or the Neighborhood Growth. Journal of Theoretical Computer Science (TCS), 6(2), 70-80. (ISI_2016: 0.643; ISI_2016_5year: 0.815)


Beitrag in wissenschaftlicher Fachzeitschrift


We deterministically compute a Delta + 1 coloring and a maximal independent set(MIS). Our greedy coloring and MIS algorithms improve the state-of-the-art algorithms running in O(Delta + log n) for a large class of graphs, i.e., graphs of (moderate) neighborhood growth with h >= 36. We also state and analyze a randomized coloring algorithm in terms of the chromatic number, the run time and the used colors. Our algorithm runs in time O(log Gsi + log* n) for Delta in Omega(log^{1+1/ log* n} n) and Gsi in O(Delta/ log^{1+1/ log* n} n). For graphs of polylogarithmic chromatic number the analysis reveals an exponential gap compared to the fastest Delta + 1 coloring algorithm running in time O(log Delta + sqrt(log n)). The algorithm works without knowledge of ? and uses less than Delta colors. To the best of our knowledge this is the ?rst distributed algorithm for (such) general graphs taking the chromatic number ? into account. We also improve on the state of the art deterministic computation of (2, c)-ruling sets.



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