image

KAPITEL7

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, 4th Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.