The classical Steiner tree problem requires a shortest tree spanning a given vertex subset within a graph
G=(V,E). An important variant is the Steiner tree problem in rectilinear metric. Only recently two algorithms were found which achieve
better approximations than the ``traditional'' one with a factor of
3/2. These algorithms with an approximation ratio of
11/8 are quite slow and run in time
and
. A new simple implementation reduces the time to
. As our main result we present efficient parametrized algorithms which reach a performance ratio of
11/8 + ɛ for any
ɛ > 0 in time
, and a ratio of
in time
.
Received December 2, 1993, and in revised form July 24, 1996.