Next: Das Maximum-Traveling-Salesman-Problem
Up: Geometrische Probleme
Previous: Dispersionsprobleme
Bei der Optimierung eines Netzwerkes tritt oft die Situation
ein, daß man die Menge der bestehenden direkten Verbindungen reduzieren
muß, um Kosten zu sparen. Dabei ist es meist unerwünscht,
daß sich die Länge des kürzesten Weges zwischen zwei Knoten des Netzwerkes
gegenüber der ursprünglichen Entfernung um einen zu großen
Faktor erhöht. Für ein Teilnetzwerk bezeichnet man den größten derartig
auftretenden Faktor als den sogenannten Streckungsfaktor;
sind alle ursprünglich voneinander erreichbaren
Knoten auch weiterhin verbunden (wenn auch durch möglicherweise
durch längere Wege), so nennt man das Teilnetzwerk einen
Spanner des Netzwerkes. Spanner werden schon seit einer Reihe
von Jahren algorithmisch untersucht. Neben der Bedeutung für die
Netzwerkoptimierung treten sie auch überall da auf, wo man eine
große Menge von Informationen über Einzelverbindungen durch
eine wesentlich kleinere Zahl ersetzen will, ohne daß dadurch
die Information über Kosten oder Entfernungen zu stark geändert
wird.
Ist man an Spannern minimalen Gewichts interessiert, so sind
Baumspanner besonders interessant, d.h. Teilnetzwerke,
aus denen keine weiteren Kanten mehr entfernt werden
können, ohne daß ursprünglich vorhandene Verbindungen
vollständig verloren gehen.
Cai und Corneil haben vor einigen Jahren gezeigt, daß
die Existenz eines 2-Baumspanners in beliebigen Netzwerken
in polynomieller Zeit überprüft werden kann, die Entscheidung
über die Existenz eines 4-Baumspanners hingegen NP-vollständig ist.
Die Komplexität von 3-Baumspannern in beliebigen Netzwerken ist schon
seit längerem offen.
Eine Klasse von Netzwerken von großer Bedeutung sind die sogenannten
planaren Graphen - also Netzwerke, die ohne Überkreuzung von Kanten
in der Ebene darstellbar sind. Da es in planaren Graphen
besonders einfache Beziehungen zwischen den in einem Baumspanner
verbleibenden und den entfernten Kanten gibt (die entfernten Kanten
bilden einen Baumspanner des Dualgraphen), war es durchaus denkbar,
daß für diese Graphenklasse schnelle Algorithmen zur Auffindung
guter Baumspanner existieren. Es gelang uns aber nachzuweisen,
daß die Frage nach einem Baumspanner mit optimalem Stretchfaktor
bereits für planare Graphen NP-schwer ist. Andererseits
entwickelten wir einen Algorithmus, der in polynomieller
Zeit entscheidet, ob ein planarer Graph einen 3-Baumspanner hat.
Zumindest für diesen Spezialfall konnten wir also eine
positive Antwort auf das Problem von Cai und Corneil finden.
Next: Das Maximum-Traveling-Salesman-Problem
Up: Geometrische Probleme
Previous: Dispersionsprobleme
Webmaster<www@zpr.uni-koeln.de>
1999-07-28