176 CHAPTER 8 Timing Optimization for Multiterminal Interconnects 8.3 VIA PLACEMENT ALGORITHMS FOR INTERCONNECT TREES Efficient near-optimal algorithms for placing vias among interplane interconnects are investigated in this section. Based on the aforemen- tioned heuristic described in Section 8.2.1, an efficient algorithm for interplane interconnect trees is presented in Section 8.3.1. A second algorithm that places interplane vias to minimize the delay for the particular case of interconnect trees with a single critical branch is discussed in Section 8.3.2. 8.3.1 Interconnect Tree Via Placement Algorithm (ITVPA) The via placement optimization algorithm for multiterminal nets is presented in this section. The input to the algorithm is an interplane interconnect tree in which the minimum length of the segments, the weight of the sinks, and the length of the allowed intervals