ABSTRACT
This chapter presents a highly scalable heuristic for computing near-optimal Steiner trees. It describes in detail two of the key batched greedy algorithm (BGA) subroutines and explores the new divide-and-conquer method for computing the set of O(nlogn) triples used by BGA. The chapter explains the new data structure for computing bottleneck edges and discusses experimental results comparing BGA with implementations of rectilinear and octilinear Steiner tree heuristics and exact algorithms on test cases both randomly generated and extracted from very large-scale integration designs. C. Chiang et al. proposed a simple heuristic for constructing octilinear Steiner trees that computes a rectilinear Steiner tree for the terminals and then iteratively reduces tree length by using diagonal wires to reroute tree edges and by sliding Steiner points. Comprehensive experimental evaluation indicates that the iterated 1-Steiner heuristic of A. B. Kahng and G. Robins significantly outperforms in solution quality the rectilinear Steiner tree heuristics proposed prior to 1992.
