Name
Abstract | ||
|---|---|---|
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^e)-approximation algorithms for arbitrarily small values of e0, improving on the previously known O(k^0.5)-approximation. Our techniques also solve the graph Steiner arborescence problem with an O(k^e) 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. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1109/DATE.1998.655889 | Paris |
Keywords | Field | DocType |
improved approximation bound,weighted graph,group steiner problem,minimum-cost routing tree,k disjoint group,practical problem,approximation algorithm,java implementation,polynomial-time o,graph steiner arborescence problem,vlsi layout,cost function,very large scale integration,tree graphs,routing,computer science,network routing,polynomials,clustering,vlsi,java,integrated circuit layout,approximation algorithms,connectivity,steiner trees,placement,polynomial time | Integrated circuit layout,Graph,Combinatorics,Disjoint sets,Steiner tree problem,Computer science,Parallel computing,Theoretical computer science,Arborescence,Cluster analysis,Very-large-scale integration,Vlsi layout | Conference |
ISBN | Citations | PageRank |
0-8186-8359-7 | 4 | 0.72 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| C. S. Helvig | 1 | 27 | 4.12 |
| G. Robins | 2 | 185 | 28.16 |
| A. Zelikovsky | 3 | 289 | 38.30 |