This thesis considers some VLSI interconnects sizing and ordering problems occurring in VLSI chip design. The first topic discussing design implementation of interconnect in the VLSI design flow, a task known also as routing. We will present the interconnection problem in a generalized approach where the two aspects of routing, namely the wiring patterns and their widths are simultaneously optimized to yield minimum Power Delay Product interconnect. The simultaneous handling of routing pattern and sizing is obtained by employing recent network flow results using simulated annealing scheme. 

The second topic presents several optimization problems occurring in VLSI interconnect, Networks on Chip (NoC) design and 3D VLSI integration, all possessing closed-form solutions obtained by well-solvable Quadratic Assignment Problems (QAP). The first type of problems deals with the optimal ordering of signals in a bus bundle such that the switching power, delay and noise interference are minimized. We extend a known solution of ordering the signals in a bus bundle to minimize the impact of the 1^st order wire-to-wire parasitic capacitance occurring between adjacent wires into a model accounting also secondary components of wire-to-wire parasitic capacitances. The second type of problems arises in the mapping of computation tasks into array of processors sharing a common bus, such as those found in NoC. We show a QAP closed-form solution to the optimal mapping problem which simultaneously minimizes the switching power and the average delay of the bus.  The third problem deals with the optimization of 3D VLSI, vertically stacking ordinary ICs.  Some of the above problems involve -distance Traveling Salesman Problem (TSP), where costs are evaluated for elements located at -distance apart along the tour. We show a simple proof that these are well-solvable problems and obtain their solution. This is then generalized to well-solvable QAPs obtained by superposition of such TSPs. A simple proof shows that if -distance TSPs are well-solvable, so is the QAP obtained by their sum, where the solution of -distance TSPs dominates all the others.