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:swb:ch1-200401426 |
| Date | 24 September 2004 |
| Creators | Baumann, Tobias |
| Contributors | TU Chemnitz, Fakultät für Informatik, Prof. Dr. Hanno Lefmann, Prof. Dr. Hanno Lefmann, Dr. Ulrich Tamm |
| Publisher | Universitätsbibliothek Chemnitz |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | deu |
| Detected Language | German |
| Type | doc-type:masterThesis |
| Format | application/pdf, text/plain, application/zip |
Page generated in 0.0014 seconds