de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Near-optimal distributed edge

MPG-Autoren

Dubhashi,  Devdatt P.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Panconesi,  Alessandro
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-94-136.pdf
(beliebiger Volltext), 9MB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Dubhashi, D. P., & Panconesi, A.(1994). Near-optimal distributed edge (MPI-I-94-136). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-B794-F
Zusammenfassung
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