Item Details

Print View

An Approximation Scheme for the Group Steiner Tree Problem

Helvig, CS; Robins, G; Zelikovsky, A
Format
Report
Author
Helvig, CS
Robins, G
Zelikovsky, A
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
Language
English
Date Received
2012-10-29
Published
University of Virginia, Department of Computer Science, 1997
Published Date
1997
Rights
All rights reserved (no additional license for public reuse)
Collection
Libra Open Repository

Availability

Access Online