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.