Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • search hit 7 of 102
Back to Result List

Packing Paths and Steiner Trees: Routing of Electronic Circuits.

Please always quote using this URN: urn:nbn:de:0297-zib-1113
  • One of the challenging problems in the design of electronic circuits is the so-called routing problem. Roughly speaking, the task is to connect so-called terminal sets via wires on a predefined area. In addition, certain design rules are to be taken into account and an objective function such as the wiring length must be minimized. The routing problem in general is too complex to be solved in one step. Depending on the user's choice of decomposing the chip design problem into a hierarchy of stages, on the underlying technology, and on the given design rules, various subproblems arise. We discuss several variants of practically relevant routing problems and give a short overview on the underlying technologies and design rules. Many of the routing problems that come up this way can be formulated as the problem of packing so-called Steiner trees in certain graphs. We consider the Steiner tree packing problem from a polyhedral point of view and present three possibilities to define an appropriate polyhedron. Weighing their pros and cons we decide for one of these polytopes and sketch some of our investigations.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Alexander Martin, Robert Weismantel
Document Type:ZIB-Report
Date of first Publication:1993/07/22
Series (Serial Number):ZIB-Report (SC-93-15)
ZIB-Reportnumber:SC-93-15
Published in:Appeared in: CWI Quarterly, Centrum voor Wiskunde en Informatica, vol. 6, no. 3, 1993, pp. 185-204
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.