Fachbereich Informatik

Steiner et al.

Für unsere Untersuchungen zu NP-schweren Problemen haben wir uns das Steinerbaumproblem herausgesucht:

Steinerbäume bilden wegen ihrer kürzeren Gesamtkantenlänge eine attraktive Alternative zu herkömmlichen aufspannenden Bäumen. Leider ist das Problem, einen minimalen Steinerbaum zu finden (im Gegensatz zu dem Problem, einen minimalen aufspannenden Baum zu finden) NP-schwer; dies gilt sogar für scheinbar einfache Spezialfälle, wie z.B. bei Verwendung der Manhattan-Metrik.

Nachdem wir in früheren Jahren schnelle Heuristiken entwickelt haben, die dem Optimum sehr nahe kommen (ca. 25%), haben wir uns in der jüngeren Vergangenheit auf die Entwicklung von Algorithmen spezialisiert, die für kleinere Probleminstanzen das Optimum exakt berechnen; dabei haben wir einen Weltrekord aufgestellt -- unser Verfahren löst jedes Problem bis zur Größe von 55 Punkten und viele größere Probleme bis zu 100 Punkten.

Veröffentlichungen

  • M. Kaufmann, S. Gao, K. Thulasiraman: "On Steiner Minimal Trees in Grid Graphs and its Application to Homotopic Routing", Journal of Circuits, Systems and Computers, Vol. 6, No. 1, pp. 1-13, 1996.
  • P. Berman, U. Fößmeier, M. Karpinski, M. Kaufmann, A. Zelikovsky: "Approaching the 5/4 -- Approximation for Rectilinear Steiner Trees", Proc. 2nd European Symposium on Algorithms (ESA '94), LNCS, Springer Verlag, pp. 60-71, 1994.
  • U. Fößmeier, M. Kaufmann, A. Zelikovsky: "Faster Approximation Algorithms for the Rectilinear Steiner Problem", Discrete & Computational Geometry 18, pp. 93-109, 1997.
  • U. Fößmeier and M. Kaufmann: "Solving Rectilinear Steiner Tree Problems Exactly in Theory and Practice", Proc. 5th European Symposium on Algorithms (ESA '97), LNCS 1284, Springer Verlag, pp. 171-185, 1997.

Datenschutzeinstellungen

Auf unserer Webseite werden Cookies verwendet. Einige davon werden zwingend benötigt, während es uns andere ermöglichen, Ihre Nutzererfahrung auf unserer Webseite zu verbessern. Ihre getroffenen Einstellungen können jederzeit bearbeitet werden.

oder

Essentiell

in2code

Videos

in2code
YouTube
Google