University thesis:
Diplomarbeit, Technische Universität Chemnitz, 2004
Footnote:
Description:
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. ; Das Problem, einen Graphen mit einer gegebenen Anzahl Farben zufärben, ist als NP-vollständig bekannt. Hier werden einigeAlgorithmen vorgestellt, die für dieses Problem eine guteApproximation liefern. Des Weiteren wird ein allgemeinesFärbungsverfahren hergeleitet, das für k-färbbare Graphenden bisher besten existierenden Algorithmus darstellt. Es könnenk-färbbare Graphen mit ~O(n^a(k)) Farbengefärbt werden, wobei a(2)=0, a(3)=3/14 unda(k) = 1 - 6/(k+4+3(1-2/k)/(1-a(k-2))) fürk >= 4 gilt [20]. Diese Formel wurde fürneue Basisalgorithmen verallgemeinert.