Minimum density interconnection trees

A new minimum density objective for spanning and Steiner tree constructions is discussed. This formulation is motivated by the need for balanced usage of routing resources to achieve minimum-area VLSI layouts. Efficient heuristics for constructing low-density spanning trees are presented, and it is proved that their outputs are on average within small constraints of optimal with respect to both tree weight and density. The minimum density objective can be transparently combined with a number of previous interconnection objectives (e.g., minimizing radius or skew), without affecting the solution quality with respect to these previous metrics. Extensive simulation results suggest that applications to VLSI global routing are promising