On the Minimum Density Interconnection Tree Problem

We discuss a new minimum density objective for spanning and Steiner tree constructions. This formulation ismotivated by the minimum-area layout objective, which is best achieved through balancing the usage of horizontaland vertical routing resources. We present two efficient heuristics for constructing low-density spanning trees andprove that their outputs are on average within small constants of optimal with respect to both tree cost anddensity. Our proof techniques suggest a non-uniform lower bound schema which can afford tighter estimates ofsolution quality for a given problem instance. Furthermore, the minimum density objective can be transparentlycombined with a number of previous interconnection objectives (e.g., minimizing tree radius or skew) withoutaffecting solution quality with respect to these previous metrics. Extensive simulation results suggest that applicationsto VLSI global routing are promising