Institut für Informatik
	Frank Lauxtermann

Frank Lauxtermann:
Traveling Salesman mit Iteriertem Matching

Zweitgutachter: Prof. Dr. Volker Sperschneider

In dieser Arbeit geht es um ein neues Näherungsverfahren für das Traveling Salesman Problem. Auf dem Problemgraphen sollen je zwei Knoten durch ein Maximum-Weight-Matching miteinander verbunden werden. Jede dieser Verbindungen soll dann einen neuen Knoten (Cluster) darstellen, in dem ein (oder mehrere) Hamilton-Pfade gespeichert sind. Auf den enstehenden Clustergraphen werden erneut (iterativ) Matchings durchgeführt, bis schließlich nur noch zwei Cluster existieren. Die Verbindung dieser beiden Cluster liefert dann eine Tour von guter Qualität.

• Inhaltsverzeichnis
• Einleitung
• Zusammenfassung und Ausblick

Postscript der gesamten Arbeit (gzipped, 335 kB)