In dieser Veranstaltung sollen Algorithmen zur Lösung des
Färbungsproblems behandelt werden.
Da das Problem, die Knoten eines beliebigen Graphen mit
möglichst wenig Farben so zu färben, dass benachbarten Knoten
stets verschiedene Farben zugeordnet werden, bekanntermaßen
NP-vollständig ist, sollen in dieser Veranstaltung auch sogenannte
"heuristische Verfahren" untersucht werden.
Heuristische Verfahren produzieren eine "schnelle" Lösung des
Problems, finden dabei aber in der Regel nicht die optimale
Lösung. Daher sind hier Fragestellungen nach der "Güte" der
erzielbaren Lösung angebracht.
Weitere Varianten, die untersucht werden sollen, wenden einen
probabilistischen Ansatz an, d. h. sie "würfeln" bei der
Lösung des Problems den nächsten Schritt, oder nutzen
zur Steigerung der Ausführungsgeschwindigkeit mehrere Prozessoren
gleichzeitig, werden also parallel ausgeführt.