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.