An efficient 3-approximation algorithm for the Steiner tree problem with the minimum number of Steiner points and bounded edge length

Abstract

<jats:p>We present improved algorithms for the Steiner tree problem with the minimum number of Steiner points and bounded edge length. Given <jats:italic>n</jats:italic> terminal points in a 2D Euclidean plane and an edge length bound, the problem asks to construct a spanning tree of <jats:italic>n</jats:italic> terminal points with minimal Steiner points such that every edge length of the spanning tree is within the given bound. This problem is known to be NP-hard and has practical applications such as relay node placements in wireless networks, wavelength-division multiplexing(WDM) optimal network design, and VLSI design. The best-known deterministic approximation algorithm has <jats:italic>O</jats:italic>(<jats:italic>n</jats:italic><jats:sup>3</jats:sup>) running time with an approximation ratio of 3. This paper proposes an efficient approximation algorithm using the Voronoi diagram that guarantees an approximation ratio of 3 in <jats:italic>O</jats:italic>(<jats:italic>n</jats:italic> log <jats:italic>n</jats:italic>) time. We also present the first exact algorithm to find an optimal Steiner tree for given three terminal points in constant time. Using this exact algorithm, we improve the 3-approximation algorithm with better performance regarding the number of required Steiner points in <jats:italic>O</jats:italic>(<jats:italic>n</jats:italic> log <jats:italic>n</jats:italic>) time.</jats:p>