6 Färbung von Graphen
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. ...
Get Algorithmische Graphentheorie, 5th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
