View Related Documents

Abstract

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.

Fulltext Preview

Image of the first page of the fulltext document