Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Abstract:
Vertex Cover finden in vielen Bereichen, wie etwa in Wireless Sensory Networks, der IT-Sicherheit oder der Bioinformaik Anwendung. Das Vertex Cover Problem ist allerdings NP-schwer, daher ist es häufig relevant,
Vertex Cover mit einem geringen Approximationsfaktor zu bestimmen. Für
diese Arbeit wurden mehrere Approximationen und Heuristiken für das
Weighted Vertex Cover Problem implementiert. Diese wurden, vor allem im Hinblick auf ihre Approximationsfaktoren, auf eine Vielzahl von Testgraphen angewendet und miteinander verglichen. Unter den implementierten Algorithmen befinden sich drei Approximationen, welche dem relativ neuen Ansatz des Structural Rounding Framework von Demaine et al. folgen. Zwar gibt es mehrere praktische Beurteilungen von Vertex Cover Approximationen, allerdings wurde der Ansatz des Structural Roundings bis jetzt hauptsächlich durch die Berechnung eines Odd Cycle Transversals von Lavallee et al. behandelt. Die in dieser Arbeit implementierten Structural Rounding Algorithmen editieren jeweils zu Co-Graphen, Cluster-Graphen und azyklischen Graphen. Außerdem
wurden zwei bekannte 2-Approximationen und eine Heuristik implementiert.
Auf den von uns getesteten Graphen erreichen die Structural Rounding
Algorithmen in den meisten Fällen bessere Approximationsfaktoren als die
bekannten 2-Approximationen. Structural Rounding zu azyklischen Graphen
erreicht dabei bis auf wenige Ausnahmen die besten Ergebnisse.