### Technical Report No. 17, September 1989 - Abstract

**Gabriele Reich, Peter Widmayer:**

*Beyond Steiner's Problem: A VLSI Oriented Generalization*

*This report is not available in electronic form!*

We consider a generalized version of Steiner's problem in graphs, motivated by the wire
routing phase in physical VLSI design: given a connected, undirected distance graph
with groups of required vertices and Steiner vertices, find a shortest connected subgraph
containing at least one required vertex of each group.
We propose two efficient approximation algorithms computing different approximate
soluations in time *O(|E| + |V|*log |V|)*
and in time *O(g*|E| + |V|*log |V|)*, respectively,
where *|E|* is the number of edges in the given graph, *|V|*
is the number of vertices, and *g* is the number of groups.
The latter algorithm propagates a set of wavefronts with different distances
simultaneously through the graph; it is interesting in its own right.