Diskussion:Steinerbaumproblem
aus Wikipedia, der freien Enzyklopädie
[Bearbeiten] Komplexität
Ist das Steinerbaumproblem schon bei der hier beschriebenen Version ohne Kantengewichte NP-schwer? --Head 
11:37, 9. Jun 2005 (CEST)
- Ja, das Steinerbaumproblem ist selbst bei Einschränkung auf bipartite Graphen ohne Kantengewichte NP-schwer. --Coma 19:44, 9. Jun 2005 (CEST)
In der beschriebenen Form habe ich zuerst das Verständnis entwickelt, dass die Menge V einfach gegeben und fest ist. Mittlerweile glaube ich verstanden zu haben, dass man die Hilfsknoten und Kanten frei wählen kann, damit ein opt. Baum entsteht. Ist das richtig und hätte man das aus dem Artikel herauslesen können?
- Eine Instanz besteht aus einer Knotenmenge V, von denen einige zur Menge der Terminale T gehören, Kanten E zwischen den Knoten V und Gewichten auf den Kanten. Die Lösung einer Instanz ist ein Baum, der alle Knoten von T verbindet. Eine optimale Lösung ist eine, die die Summer der Gewichte der dabei verwendeten Kanten minimiert. Das Problem besteht darin, eine optimale Lösung für eine Instanz zu finden. Man sucht also nach einem Alg, der eine optimale Lösung für eine beliebige Instanz finden kann. Das ist eigentlich ganz leicht. Schwer ist es, einen Alg. anzugeben, der das in vernünftiger Zeit tut. Das ist im wesentenlichen dass, was man aus dem Artikel rauslesen können muss?! --Koethnig 01:25, 1. Apr 2006 (CEST)
[Bearbeiten] Literatur
Hab jetzt schon an mehreren Stellen von folgendem Paper gelesen: G. Robins, A. Zelikovsky, Improved Steiner tree approximation in graphs, In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2000, 770-779. Sollte man das wohl noch mit aufnehmen?
