Mathematical Programming Computation, Volume 9, Issue 2, June 2017

Font Size:  Small  Medium  Large

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

Stefan Hougardy, Jannik Silvanus, Jens Vygen

Abstract


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.

Full Text: PDF

mpc footer
© MPS 2008-2017