Loading...
Please wait, while we are loading the content...
Similar Documents
Improved Approximation Bounds for the Group Steiner Problem (1998)
| Content Provider | CiteSeerX |
|---|---|
| Author | Helvig, C. S. Robins, Gabriel Zelikovsky, Alexander |
| Description | Given a weighted graph and a family of k disjoint groups of nodes, the Group Steiner Problem asks for a minimum-cost routing tree that contains at least one node from each group. We give polynomial-time O(k ffl )-approximation algorithms for arbitrarily small values of ffl ? 0, improving on the previously known O(k 1 2 )-approximation. Our techniques also solve the graph Steiner arborescence problem with an O(k ffl ) approximation bound. These results are directly applicable to a practical problem in VLSI layout, namely the routing of nets with multi-port terminals. Our Java implementation is available on the Web. 1 Introduction The classical Steiner problem can be formulated as follows: given an undirected weighted graph G = (V; E) and M ` V , find a minimum-cost tree that spans all of M . Nodes in V \Gamma M (referred to as Steiner nodes) may be optionally included in order to reduce the total tree cost [11]. In this paper, we address a generalization of this problem, nam... |
| File Format | |
| Language | English |
| Publisher Date | 1998-01-01 |
| Publisher Institution | In Proc. Conference on Design Automation and Test in Europe |
| Access Restriction | Open |
| Subject Keyword | Minimum-cost Tree Small Value Multi-port Terminal Disjoint Group Steiner Node Practical Problem Approximation Bound Weighted Graph Vlsi Layout Java Implementation Classical Steiner Problem Graph Steiner Arborescence Problem Minimum-cost Routing Tree Approximation Algorithm Undirected Weighted Graph Total Tree Cost Group Steiner Problem |
| Content Type | Text |
| Resource Type | Article |
