Constructing minimal spanning/Steiner trees with bounded pathlength

摘要

This paper presents an exact algorithm and two heuristics forsolving the Bounded path length Minimal Spanning Tree (BMST) problem.The exact algorithm which is based on iterative negative-sum-exchange(s)has polynomial space complexity and is hence more practical than themethod presented by Gabow. The first heuristic method (BKRUS) is basedon the classical Kruskal MST construction. For any given value ofparameter ε, the algorithm constructs a routing tree with thelongest interconnection path length at most (1+ε).R, andempirically with cost at most 1.19 times cost (BMST*) where R is thelength of the direct path from the source to the farthest sink and BMST*is the optimal bounded path length MST. The second heuristic combinesBKRUS and negative-sum-exchange(s) of depth 2 to improve results.Extensions of these techniques to the bounded path length MinimalSteiner Trees, using the Elmore delay model are presented as well.Empirical results demonstrate the effectiveness of these algorithms on alarge benchmark set