Volker Turau, Christoph Weyer
Algorithmische
Graphentheorie

Algorithmische Graphentheorie


Kapitel 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 der perfekten Graphen näher vorgestellt.

Kapitelübersicht

  1. Einleitung
  2. Einführung
  3. Bäume
  4. Suchverfahren in Graphen
  5. Entwurfsmethoden für die algorithmische Graphentheorie
  6. Färbung von Graphen
  7. Perfekte Graphen
    1. Einführung
    2. Kreisfreie Orientierungen
    3. Transitiv orientierbare Graphen
    4. Permutationsgraphen
    5. Chordale Graphen
    6. Intervallgraphen
    7. Literatur
    8. Aufgaben
  8. Flüsse in Netzwerken
  9. Anwendungen von Netzwerkalgorithmen
  10. Kürzeste Wege
  11. Approximative Algorithmen