7 Perfekte Graphen
Das letzte Kapitel hat gezeigt, dass die Bestimmung minimaler Färbungen für beliebige Graphen eine schwere Aufgabe ist. In Kapitel 11 werden hierfür noch weitere Belege angegeben. Es stellt sich daher die Frage, ob es neben bipartiten und planaren Graphen noch weitere Klassen von Graphen gibt, für die effizient eine minimale Färbung bestimmt werden kann. Dieses Kapitel gibt eine Einführung in die Klasse der perfekten Graphen. Für Graphen dieser Klasse lassen sich in linearer Zeit nicht nur minimale Färbungen bestimmen, sondern auch die Unabhängigkeitszahl und die Cliquenzahl. Es werden Algorithmen für vier Unterklassen ...
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.
