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

DOI10.1007/S12532-016-0110-1MaRDI QIDQ1699613zbMATH OpenOpenAlexFDO

Authors Stefan Hougardy, Jannik Silvanus, Jens Vygen

Publication date 23 February 2018

Published in Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.0492

zbMATH Keywords

dynamic programmingexact algorithmgraph algorithmsSteiner tree problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Combinatorial optimization (90C27) Dynamic programming (90C39)

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 $din3,4,5$, whose Hanan grids contain up to several millions of edges.

Recommendations

• Solving rectilinear Steiner tree problems exactly in theory and practice
• scientific article; zbMATH DE number 1947438
• A Faster Algorithm for the Steiner Tree Problem
• scientific article; zbMATH DE number 1424547
• Faster exact algorithms for steiner trees in planar networks

Cites work

• A comparison of Steiner tree relaxations
• A dual ascent approach for steiner tree problems on a directed graph
• A Dynamic Programming Approach to Sequencing Problems
• A note on two problems in connexion with graphs
• An algorithm for the steiner problem in graphs
• An edge elimination test for the Steiner problem in graphs
• Approaches to the Steiner Problem in Networks
• Combinatorial optimization in VLSI design
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Dual heuristics on the exact solution of large Steiner problems
• Dynamic programming for minimum Steiner trees
• Faster algorithm for optimum Steiner trees
• Fibonacci heaps and their uses in improved network optimization algorithms
• scientific article; zbMATH DE number 1947441 (Why is no real title available?)
• scientific article; zbMATH DE number 1424547 (Why is no real title available?)
• On Steiner Minimal Trees with Rectilinear Distance
• On Steiner’s Problem with Rectilinear Distance
• On the Exact Location of Steiner Points in General Dimension
• Practical Partitioning-Based Methods for the Steiner Problem
• Preprocessing Steiner problems from VLSI layout
• Reducibility among combinatorial problems
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• Solving Steiner tree problems in graphs to optimality
• Solving the Steiner Tree Problem on a Graph Using Branch and Cut
• Speeding up dynamic programming with representative sets. An experimental evaluation of algorithms for Steiner Tree on tree decompositions
• Steiner tree approximation via iterative randomized rounding
• The steiner problem in graphs
• The Steiner tree problem on graphs: inapproximability results
• The Traveling-Salesman Problem and Minimum Spanning Trees

Cited in

(21)

• A robust and scalable algorithm for the Steiner problem in graphs
• Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology
• Robust reoptimization of Steiner trees
• Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees
• The rainbow Steiner tree problem
• Faster exact algorithms for steiner trees in planar networks
• scientific article; zbMATH DE number 1947438 (Why is no real title available?)
• Strong Steiner tree approximations in practice
• scientific article; zbMATH DE number 1424547 (Why is no real title available?)
• scientific article; zbMATH DE number 1424549 (Why is no real title available?)
• New algorithms for Steiner tree reoptimization
• The PACE 2018 parameterized algorithms and computational experiments challenge: the third iteration
• An Exact Algorithm for the Steiner Forest Problem
• A Faster Algorithm for the Steiner Tree Problem
• Implications, conflicts, and reductions for Steiner trees
• Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
• Stronger path‐based extended formulation for the Steiner tree problem
• A linear programming based approach to the Steiner tree problem with a fixed number of terminals
• Solving Steiner trees: Recent advances, challenges, and perspectives
• New algorithms for Steiner tree reoptimization
• Faster algorithms for Steiner tree and related problems: from theory to practice

Describes a project that uses

Uses Software

• SteinLib
• DIMACS

This page was built for publication: Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1699613)