# 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:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-94-136.pdf | 9143 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},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-94-136},`

` MONTH = {July},`

` YEAR = {1994},`

` ISSN = {0946-011X},`

`}`