Diese Arbeit beschäftigt sich mit kombinatorischen Problemen, welche als Verallgemeinerungender 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.