An Approximation Scheme For The Group Steiner Tree Problem

Report
Authors:Helvig, CS, Department of Computer ScienceUniversity of Virginia Robins, G, Department of Computer ScienceUniversity of Virginia Zelikovsky, A, Department of Computer ScienceUniversity of Virginia
Abstract:

We address a practical problem which arises in several areas, including network design and VLSI circuit layout. Given an undirected weighted graph G = (V, E) and a family N = {N1, . . . ,N;.} of k disjoint groups of nodes N; Q V, the Group Steiner Problem asks for a minimum-cost tree which contains at least one node from each group Ng. In this paper, we give polynomial-time 0(k‘)- approximation algorithms for any fixed 5 > 0. This result improves the previously known 0(k)- approximation. We also apply our approximation algorithms to the Steiner problem in directed graphs, while guaranteeing the same performance ratio.
Note: Abstract extracted from PDF file via OCR

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Helvig, CS, G Robins, and A Zelikovsky. "An Approximation Scheme For The Group Steiner Tree Problem." University of Virginia Dept. of Computer Science Tech Report (1997).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1997