TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1993

COGA 5-Wheel

Page Content

to Navigation

Preprints 1993

Two-Layer Wiring with Pin Preassignments
Citation key Report-345-1993
Author Paul Molitor and Uwe Sparmann and Dorothea Wagner
Title of Book Proc. of the 7'th International Conference on VLSI Design, 1994
Year 1993
Number 345
Institution Technische Universität Berlin, Institut für Mathematik
Abstract We examine the constrained via minimization problem with pin preassignments (CVMPP) which arises in connection with hierarchical Physical synthesis. Let $A$ be a circuit composed of subcircuits $B,\ C,\ D,\ łdots$. Assume that the placement and routing phase together with the 2-layer wiring of the subcircuits, and the placement and routing phase without the 2-layer wiring of $A$ are completed. CVMPP ist the problem of finding a 2-layer wiring of $A$ which is induced by the 2-layer wirings of the subcircuits and which contains a minimal amount of vias on this condition. First, we show that CVMPP is NP-complete. In the case that the wiring of the power supply nets has already been generated we present a polynomial time algorithm solving CVMPP.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe