Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

The Steiner Tree Packing Problem in VLSI-Design.

Please always quote using this URN: urn:nbn:de:0297-zib-1328
  • In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Martin Grötschel, Alexander Martin, Robert Weismantel
Document Type:ZIB-Report
Date of first Publication:1994/01/20
Series (Serial Number):ZIB-Report (SC-94-02)
Published in:Appeared in: Mathematical Programming 78 (1997) 265-281
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.