Minimum Spanning Tree und 2-Approximation der TSP-Tour

Der Minimum Spanning Tree zu einem geg. Graphen ist ein Baum, der alle Knoten des Graphen enthält und dessen Summe aller Kantengewichte minimal ist. Man kann zeigen, daß mit diesem Baum das Problem des Handlungsreisenden (TSP) approximiert werden kann, wobei die approximierte Tour maximal doppelt so lang ist wie die optimale TSP-Tour.

Inhalt des Vortrags:

• genaue Vorstellung des Problems
• Definition und Konstruktion des Minimum Spanning Tree in Zeit O
• 2-Approximation der TSP-Tour mit Hilfe des Minimum Spanning Tree

Literatur:

Rolf Klein, Algorithmische Geometrie, Addison Wesley 1997
Kapitel 5.3.3 S. 225-228.

F. Preparata, I. Shamos. Computational Geometry. Springer Verlag, 1985. (Kapitel 6.1)

E. Horowitz, S. Sahni. Algorithmen. Springer Verlag, 1978. (Kapitel 4.6)

Ingo Wegener. Skript zur Vorlesung 'Effiziente Algorithmen'. Uni Dortmund. 1991. (Kapitel 5.3)

Betreuer:
Thomas Kamphans