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

作     者：Hougardy, Stefan Silvanus, Jannik Vygen, Jens 

作者机构：Univ Bonn Res Inst Discrete Math Bonn Germany 

出 版 物：《MATHEMATICAL PROGRAMMING COMPUTATION》 (数学规划计算)

年 卷 期：2017年第9卷第2期

页      面：135-202页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Graph algorithms Steiner tree problem Dynamic programming Exact algorithm 

摘      要：We present a new exact algorithm for the Steiner tree problem in edgeweighted 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 is an element of{3, 4, 5}, whose Hanan grids contain up to several millions of edges.