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 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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:18219 |
| Date | 02 September 2004 |
| Creators | Baumann, Tobias |
| Contributors | Lefmann, Hanno, Tamm, Ulrich, Technische Universität Chemnitz |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | German |
| Detected Language | German |
| Type | doc-type:masterThesis, info:eu-repo/semantics/masterThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0022 seconds