September 2015
Intermediate to advanced
415 pages
12h 24m
German

Am Anfang der Graphentheorie standen spezifische Probleme, die leicht, d. h. ohne großen Formalismus, zu beschreiben waren. Beispiele hierfür sind das Königsberger Brückenproblem und das Vier-Farben-Problem. Während das erste Problem sich leicht lösen ließ, wurde das zweite Problem erst 1976 nach etlichen vergeblichen Anläufen gelöst. In diesem Kapitel werden Algorithmen zur Bestimmung von minimalen Eckenfärbungen vorgestellt. Da bisher kein Algorithmus mit polynomialer Laufzeit für dieses Problem bekannt ist, werden auch Heuristiken vorgestellt. Für einige spezielle Klassen von Graphen existieren effiziente Algorithmen. ...