Handbook of Algorithms for Physical Design Automation part 53 provides a detailed overview of VLSI physical design automation, emphasizing state-of-the-art techniques, trends and improvements that have emerged during the previous decade. After a brief introduction to the modern physical design problem, basic algorithmic techniques, and partitioning, the book discusses significant advances in floorplanning representations and describes recent formulations of the floorplanning problem. The text also addresses issues of placement, net layout and optimization, routing multiple signal nets, manufacturability, physical synthesis, special nets, and designing for specialized technologies. It includes a personal perspective from Ralph Otten as he looks back on. | 502 Handbook of Algorithms for Physical Design Automation For example the tree produced by the DBS group Steiner algorithm above Figures and can be utilized as the starting point in the bounded-radius bounded-cost construction of Ref. 87 . For an arbitrary instance of the group Steiner problem with k groups this combination yields a routing tree with simultaneous provably good bounds for both tree radius and tree cost. In particular the tree resulting from this merger will have radius 1 e times the optimal radius and total cost 1 2 2 2 ln 2 Vk. times the optimal cost for any user-specified radius-cost trade-off parameter e 0. Empirical Performance of the Group Steiner Heuristic The group Steiner heuristic above compares favorably with the RW heuristic proposed by Reich and Widmayer 80 . The RW group Steiner heuristic begins by first finding the MST T for the entire set of nodes of all the groups. If a leaf node is not the last member of its group in the tree T then it may be removed. The RW heuristic then repeatedly deletes such a leaf node that is incident to the longest edge among all such nodes. On random uniformly distributed pointsets with varying predetermined group areas the DBS group Steiner algorithm described above significantly outperforms the RW algorithm especially as the group sizes and the group areas increase 78 79 . OTHER STEINER TREE METHODS Once it became known 48 49 that MST-improvement-based Steiner heuristics having worst-case performance bounds no better than the MST itself . 3 in the rectilinear plane other rectilinear Steiner heuristics with average performance approaching that of I1S were subsequently proposed 88-94 . While it is generally difficult to analytically quantify the solution quality of heuristics the I1S method was later proven to be the earliest Steiner approximation with a nontrivial performance ratio in quasi-bipartite graphs 55 56 . In 2003 Kahng et al. developed a highly scalable heuristic for .
