2006 | OriginalPaper | Buchkapitel
Improved Edge-Coloring with Three Colors
verfasst von : Łukasz Kowalik
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We show an
O
(1.344
n
)=
O
(2
0.427 n
) 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 [1]. We extend 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.