Martin Lätsch
Zentrum für Angewandte Informatik Köln
Universität zu Köln

Erkennung von Berge Graphen

Ein Graph heißt Berge Graph, wenn kein induzierter Teilgraph ein ungerades Loch oder ein ungerades Antiloch enthält. Es war lange Zeit unbekannt, ob es einen polynomiellen Algorithmus gibt, der entscheidet, ob ein Graph ein Berge Graph ist. Im Jahr 2002 entwurfen Chudnovsky und Seymour bzw. Cornuéjols, Liu und Vuskovic zwei polynomielle Algorithmen für dieses Problem. Im Vortrag werden die Grundideen des Algorithmus von Chudnovsky und Seymour vorgestellt.