Design Automation and Test in Europe (DATE '98) Improved Approximation Bounds for the Group Steiner Problem Paris, France February 23-February 26 ISBN: 0-8186-8359-7
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 e>0, 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.
Citation:
C. S. Helvig, Gabriel Robins, Alexander Zelikovsky, "Improved Approximation Bounds for the Group Steiner Problem," date, pp.406, Design Automation and Test in Europe (DATE '98), 1998 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||