Finding Optimal Solutions for Covering and Matching Problems

Diese Arbeit beschäftigt sich mit kombinatorischen Problemen, welche als Verallgemeinerungen

der beiden klassischen Graphprobleme Vertex Cover und Maximum

Matching aufgefasst werden können. Das Vertex Cover-Problem ist

wie folgt definiert. Gegeben ein ungerichteter Graph, finde eine kleinstmögliche

Knotenteilmenge, die jede Kante ¿abdeckt¿, d.h. dass einer der beiden Endpunkte

jeder Kante in der Knotenteilmenge liegt. Dieses Problem wird auch oft

¿Knoten-Überdeckungsproblem¿ genannt. Das Maximum Matching-Problem fragt

nach einer größtmöglichen Kantenteilmenge in einem ungerichteten Graphen, so

dass sich die gewählten Kanten keinen Endpunkt teilen. Dieses Problem sucht

also nach einer möglichst großen Anzahl von Knotenpaaren, die durch eine Kante

verbunden sind. In bipartiten Graphen wird dieses Problem auch oft

¿Heiratsproblem¿ genannt.

Sowohl Vertex Cover als auch Maximum Matching haben eine lange

Geschichte; diese Probleme wurden schon in den Anfangsjahren der Informatik

untersucht und sind immer noch Gegenstand der aktuellen Forschung. Es

gibt für beide Probleme viele Anwendungen, beispielsweise in der Bioinformatik,

der Computer-Chemie oder auch in der Verkehrsplanung. Maximum Matching

wird in unzähligen Anwendungen als Hilfsroutine zur Lösung anderer Aufgaben

eingesetzt.