Master-Abschlusskolloquium von Salome Gülzow (Universität Kassel): Rundreiseproblem mit Nachbarschaften auf planaren Graphen

Abstract:

Wir stellen eine Variante des Rundreiseproblems auf einem planaren Graphen vor.
Bei dieser müssen nicht alle Knoten besucht werden, sondern es sind Nachbarschaften von Knoten
auf dem Graphen gegeben, aus denen jeweils nur mindestens ein Knoten besucht werden muss.
Zunächst wird gezeigt, dass das Problem NP-schwer ist. Wenn die Reihenfolge der Nachbarschaf-
ten jedoch bekannt ist, lässt sich in polynomieller Zeit eine optimale Tour finden. Daraus wird
ein zufallsbasierter Algorithmus entwickelt, welcher die Reihenfolge der Nachbarschaften zufällig
auswählt und darauf die optimale Tour berechnet.
Außerdem stellen wir weitere Approximationsalgorithmen vor. Bei dem Nearest-Insertion-Algorithmus
wird immer die nächstliegende Nachbarschaft eingefügt. Dieser liefert aber im worst-case keine
bessere Güte als der zufallsbasierte Algorithmus. Als weiterer Ansatz wird ein Algorithmus für
das planare Gruppensteinerbaumproblem als Blackbox verwendet. Bei diesem Problem liegen die
Nachbarschaften auf dem Rand einer Fläche. Deswegen werden mehrere Varianten beschrieben,
wie so eine Fläche erhalten werden kann.

Vor diesem Vortrag, ab 16.45 Uhr, gibt es wieder Kaffee und Tee im Raum 1404.
Es sind alle herzlich dazu eingeladen.

gez. Prof. Dr. Andreas Bley