Hinweis

Bitte nutzen Sie beim Zitieren immer folgende Url:

http://nbn-resolving.de/urn:nbn:de:swb:ch1-200401426

Kurzfassung in Englisch

It is known to be an NP-complete problem to color a graph with a given number of colors. We present some approximation algorithms which come close to the desired number of colors. We also develop an algorithm that colors k-colorable graphs with ~O(n^a(k)) colors, where a(2)=0, a(3)=3/14 and
a(k)=1 - 6/(k+4+3(1-2/k)/(1-a(k-2))) for k >= 4, as presented in [20]. This formula has been generalized for new possible base algorithms.

Kurzfassung in Deutsch

Das Problem, einen Graphen mit einer gegebenen Anzahl Farben zu
färben, ist als NP-vollständig bekannt. Hier werden einige
Algorithmen vorgestellt, die für dieses Problem eine gute
Approximation liefern. Des Weiteren wird ein allgemeines
Färbungsverfahren hergeleitet, das für k-färbbare Graphen
den bisher besten existierenden Algorithmus darstellt. Es können
k-färbbare Graphen mit ~O(n^a(k)) Farben
gefärbt werden, wobei a(2)=0, a(3)=3/14 und
a(k) = 1 - 6/(k+4+3(1-2/k)/(1-a(k-2))) für
k >= 4 gilt [20]. Diese Formel wurde für
neue Basisalgorithmen verallgemeinert.

weitere Metadaten

Hinweis zum Urheberrecht