MPI-INF/SWS Research Reports 1991-2021

1. Author,Editor - 3. with BibTeX cite keys


Near-optimal distributed edge

Dubhashi, Devdatt P. and Panconesi, Alessandro

July 1994, 12 pages.

Status: available - back from printing

We give a distributed randomized algorithm to edge color a network. Given a graph $G$ with $n$ nodes and maximum degree $\Delta$, the algorithm, \begin{itemize} \item For any fixed $\lambda >0$, colours $G$ with $(1+ \lambda) \Delta$ colours in time $O(\log n)$. \item For any fixed positive integer $s$, colours $G$ with $\Delta + \frac {\Delta} {(\log \Delta)^s}=(1 + o(1)) \Delta $ colours in time $O (\log n + \log ^{2s} \Delta \log \log \Delta $. \end{itemize} Both results hold with probability arbitrarily close to 1 as long as $\Delta (G) = \Omega (\log^{1+d} n)$, for some $d>0$.\\ The algorithm is based on the R"odl Nibble, a probabilistic strategy introduced by Vojtech R"odl. The analysis involves a certain pseudo--random phenomenon involving sets at the vertices

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Dubhashi, Devdatt P. and Panconesi, Alessandro},
  TITLE = {Near-optimal distributed edge},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-94-136},
  MONTH = {July},
  YEAR = {1994},
  ISSN = {0946-011X},