ISBN 9783843911740

978-3-8439-1174-0, Reihe Mathematik

Thomas Kleefisch
Pfadüberdeckungsprobleme

153 Seiten, Dissertation Universität Köln (2013), Softcover, A5

Zusammenfassung / Abstract

In dieser Arbeit befassen wir uns mit einer Verallgemeinerung des Vertex-Cover-Problems, nämlich dem sogenannten Knoten-Pfadüberdeckungsproblem. Für einige bekannte Graphenklassen zeigen wir die NP-Vollständigkeit des zugehörigen Entscheidungsproblems und geben Bedingungen an, unter welchen das Problem polynomiell lösbar ist.

Wir führen das neue Kanten-Pfadüberdeckungsproblem ein und zeigen eine allgemeine NP-Vollständigkeit des Entscheidungsproblems. Darüber hinaus zeigen wir mit Hilfe einer verallgemeinerten Regularität die additive Approximierbarkeit des Kanten-Pfadüberdeckungsproblems.

Im zweiten Teil dieser Arbeit führen wir ein semidefinites Schnittebenenverfahren ein, welches auf den Grundlagen von Chvátal und Gomory basiert, und zeigen verschiedene strukturelle Eigenschaften. Diese Methode schränken wir abschließend auf quadratische Programme ein und betrachten auch hierfür ein Schnittebenenverfahren.