loading...
Improved Approximation Bounds for the Group Steiner Problem
Paris, France February 23-February 26
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DATE.1998.655889Design Automation and Test in Europe ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
C. S. Helvig, University of Virginia, Charlottesville
Gabriel Robins, University of Virginia, Charlottesville
Alexander Zelikovsky, University of Virginia, Charlottesville
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.