Mixed Spanning Trees: A Technique for Performance-Driven Routing

We present a new strategy for performance-driven global routing. This strategy focuses on the creation of spanning trees whose properties are under the control of the designer; we apply this strategy to construct a spanning tree with simultaneous, provable perfor-mance guarantees on total length, single-source short-est path length, and bottleneck path length. For rec-tilinear problems on n terminals in the plane, such a tree can be constructed in O(n1ogn) time. 1 Iiitroductioii There has been recent work Awerbuch el al.[2], Cong et a1.[6] and Khuller et di9]) on finding trees with properties of both shortest-path and minimumweight spanning trees. In the VLSI community, this work falls under the aegis of performance-driven global routing, the purpose being to decrease the maximum source-to-sink signal delay for a critical net without drastically increasing the total length of the interconnection. Specifically, let G = (V, E be a graph with n nodes and in positively-weighted e 1 ges. There is a distinguished vertex called the source, and all other vertices are called sinks. Let the radius of G, the length of a maximum-length shortest source-to-sink path, be R, and let the length of a minimum spanning tree of G be L. Cong et a1.[6] proposed an algorithm to construct a tree whose radius is at most (1 +E)R and whose length is at most ( 1 + 3)L. Here, E> 0 is a parameter which is chosen by the designer. Khuller et 01.[9] proposed an algorithm with similar characteristics, though their result is somewhat stronger than the work of Cong el al. in that their shortest-path results are phrased in terms of distance from the source, not graph radius. Khuller et al. also show their bounds are tight; the reader should refer to those papers for a precise statement of the results and an extensive literature survey. There is additional work on performance-driven routing. Alpert el a/.[l] observed that a tree having both shortest-path and minimum spanning tre