Blick ins Buch

Finding Optimal Solutions for Covering and Matching Problems

Hannes Moser (Autor)

Buch

230 Seiten

2010 | 1., Aufl.
Cuvillier, E (Verlag)
978-3-86955-243-9 (ISBN)

Lese- und Medienproben

Inhaltsverzeichnis (PDF)

Titel ist leider vergriffen;
keine Neuauflage

Artikel merken

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.

Sprache	englisch
Einbandart	kartoniert
Themenwelt	Mathematik / Informatik ► Informatik
Schlagworte	Hardcover, Softcover / Informatik, EDV
ISBN-10	3-86955-243-3 / 3869552433
ISBN-13	978-3-86955-243-9 / 9783869552439
Zustand	Neuware