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,
ldots`. 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.
