Symmetry Breaking Depending on the Chromatic Number or the Neighborhood Growth

back to overview

Reference

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.

Publication type

Article in Scientific Journal

Abstract

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.

Persons

Organizational Units

  • Institute of Information Systems
  • Hilti Chair of Business Process Management