On exact solutions for the rectilinear Steiner tree problem - Part I: Theoretical results
The rectilinear Steiner tree problem asks for a shortest tree connecting given points in the plane with rectilinear distance. The best theoretically analyzed algorithms for this problem are based on dynamic programming and have a running time of O (n(2) 2.62(n)) (Ganley and Cohoon), resp, n(O(root n)) (Smith). The first algorithm can solve problems of size 27, the second one is highly impractical because of the large constant in the exponent. The best implementations perform poorly even on small problem instances; the best practical results can be reached using a Branch & Bound approach (Salowe and Warme); this implementation can solve random problems of size 35 within a day, while the dynamic programming approach of Ganley and Cohoon can handle only 27 point examples. Zn this paper we improve the theoretical worst-case time bound to O (n(2) 2.38(n)), for random problem instances we prove a running time of alpha(n) with a constant alpha < 2. We have implemented our algorithms and can now solve problems of 40 points in a day using a provably good dynamic programming approach, and can solve problems of 55 points with a Branch & Bound strategy. For exponential-time algorithms, this is an enormous improvement.
rectilinear steiner trees algorithms dynamic programming implementation worst-case analysis random instances