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.
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 |