Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
  DetailsÜbersicht

Freigegeben
Bericht

Coloring k-colorable graphs in constant expected parallel time

MPG-Autoren
/persons/resource/persons215941

Kučera,  Luděk
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

MPI-I-93-110.pdf
(beliebiger Volltext), 11MB

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

Kučera, L.(1993). Coloring k-colorable graphs in constant expected parallel time (MPI-I-93-110). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0014-B745-1
Zusammenfassung
A parallel (CRCW PRAM) algorithm is given to find a $k$-coloring of a graph randomly drawn from the family of $k$-colorable graphs with $n$ vertices, where $k = \log^{O(1)}n$. The average running time of the algorithm is {\em constant}, and the number of processors is equal to $|V|+|E|$, where $|V|$, $|E|$, resp. is the number of vertices, edges, resp. of the input graph.