max planck institut
informatik

# MPI-I-94-136

## Near-optimal distributed edge

### Dubhashi, Devdatt P. and Panconesi, Alessandro

MPI-I-94-136. July 1994, 12 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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
Acknowledgement:
References to related material:

MPI-I-94-136.pdf9143 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-136
BibTeX
@TECHREPORT{DubhashiPanconesi94,
AUTHOR = {Dubhashi, Devdatt P. and Panconesi, Alessandro},
TITLE = {Near-optimal distributed edge},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},