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

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Improved Edge Coloring with Three Colors

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44835

Kowalik,  Lukasz
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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

Kowalik, L. (2006). Improved Edge Coloring with Three Colors. In Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006 (pp. 90-101). Berlin, Germany: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-2328-9
Zusammenfassung
We show an $O(1.344^n) = O(2^{0.427n})$ algorithm for edge-coloring an n-vertex graph using three colors. Our algorithm uses polynomial space. This improves over the previous, $O(2^{n/2})$ algorithm of Beigel and Eppstein. We apply a very natural approach of generating inclusion-maximal matchings of the graph. The time complexity of our algorithm is estimated using the “measure and conquer” technique.