Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm

  • We present a new exact algorithm for the Steiner tree problem in edge-weighted graphs. Our algorithm improves the classical dynamic programming approach by Dreyfus and Wagner. We achieve a significantly better practical performance via pruning and future costs, a generalization of a well-known concept to speed up shortest path computations. Our algorithm matches the best known worst-case run time and has a fast, often superior, practical performance: on some large instances originating from VLSI design, previous best run times are improved upon by orders of magnitudes. We are also able to solve larger instances of the d-dimensional rectilinear Steiner tree problem for d?{3,4,5}d?{3,4,5}, whose Hanan grids contain up to several millions of edges.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Stefan Hougardy, Jannik Silvanus, Jens Vygen
DOI:https://doi.org/10.1007/s12532-016-0110-1
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2016
Tag:Software; Theoretical Computer Science
Volume:9
Issue:2
Page Number:68
First Page:135
Last Page:202
Mathematical Programming Computation :MPC 2017 - Issue 2
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.