 | Hinweis zum Urheberrecht |
| |
| | | Titel Deutsch | Effiziente Färbungsalgorithmen für k-färbbare Graphen | | Titel Englisch | Efficient coloring algorithms for k-colorable graphs | | Autor | Tobias Baumann | | Betreuer | Prof. Dr. Hanno Lefmann | | Gutachter | · Prof. Dr. Hanno Lefmann
· Dr. Ulrich Tamm | | Herausgeber | TU Chemnitz, Fakultät für Informatik
| | Typ | Diplomarbeit | | Sprache | Deutsch | | DDC-Sachgruppe(n) | 510
004
| | Schlagwörter |
· Approximationsalgorithmus
· Graphentheorie
· Graphfärbung
· k-coloring
· k-Färbbarkeit
| | Abstrakt 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.
| | Abstrakt 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.
| | Erstellungsdatum | 2004-09-02 | | Speicherung seit | 2004-09-24 | | Gültig bis | 2009-09-24 | | Format | application/pdf
| | Grösse | 766 KB | | URL | http://archiv.tu-chemnitz.de/pub/2004/0142 |
|
| |
 | Unversehrtheit der Publikation |
 | Zugriffsstatistik
(Statistikdaten basieren auf den Webzugriffsdaten dieses Dokumenten- und Publikationservers.) |
MONARCH 
