Direkt zum Inhalt | Direkt zur Navigation

Benutzerspezifische Werkzeuge

Sektionen

Polynomiell lösbare Fälle

next up previous contents
Next: Realistische Problemstellungen sind -vollständig Up: Komplexität des Problems Previous: Terminologie

Polynomiell lösbare Fälle

Wie in Satz 4.3.3 gezeigt wird, liegt das STP ohne Nebenbedingungen in tex2html_wrap_inline5238 . Gemäß Kapitel 4.3.5 können zudem einige Gleichgewichtsbedingungen berücksichtigt werden. Aus der engen Verbindung zur Graphentheorie ergeben sich zudem einige Fälle, die gut lösbar sind, da es für sie Darstellungen als LPs gibt, für die die zugehörigen Polyeder ganzzahlige Ecken haben. Diese sind jedoch mit Ausnahme der ersten drei Fälle so eingeschränkt, daß eine praktische Anwendung nicht abzusehen ist. Daher soll über diese, die zumeist von DEWERRA ([dW97] [dW96]) gefunden wurden, lediglich eine tabellarische Übersicht gegeben werden. Auf die ersten drei Fälle wird in Abschnitt 4.10 nochmals näher eingegangen

Bezeichnung Beschreibung
Perfekte Graphen für jeden ind. Teilgraph gilt tex2html_wrap_inline5308
Total unimodulare Graphen Jede Submatrix der Adjazenzmatrix hat Determinante 0,1,-1
Balancierte Graphen Linegraphen von Bäumen
PROS-perfekte Graphen Graphen, die unabhängig von gewissen Parametern ein halbpreemptives JSS erlauben
Candies, Crowns, Caterpillars Spezialfälle von PROS-Perfekten Graphen
Ice-perfekte Graphen Graphen, die eine Färbung erlauben, bei der die einzelnen Farben, die an einem Knoten anliegen, aufeinanderfolgen
BOC-Graphen bipartiter Graph, der keine drei geraden Ketten enthält, die sich in ihren Endpunkten treffen


(c) Martin Loehnertz 1999