Handbook of Algorithms for Physical Design Automation part 10 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. | 5 Basic Algorithmic Techniques Vishal Khandelwal and Ankur Srivastava CONTENTS Basic Complexity Greedy Dynamic Introduction to Graph Graph Traversal Breadth First Depth First Topological Minimum Spanning Kruskal s Prim s Shortest Paths in Graphs .80 Dijkstra s Bellman Ford Network Flow Theory of Computational Convex Hull .85 Voronoi Diagrams and Delaunay Simulated This chapter provides a brief overview of some commonly used general concepts and algorithmic techniques. The chapter begins by discussing ways of analyzing the complexity of algorithms followed by general algorithmic concepts like greedy algorithms and dynamic programming. This is followed by a comprehensive discussion on graph algorithms including network flow techniques. This is followed by discussions on NP completeness and computational geometry. The chapter ends with the description of the technique of simulated annealing. BASIC COMPLEXITY ANALYSIS An algorithm is essentially a sequence of simple steps used to solve a complex problem. An algorithm is considered good if its overall runtime is small and the rate at which this runtime increases with the problem size is small. Typically this runtime complexity is analytically measured modeled as a function of the total number of elements in the input problem. To make this analysis simpler several notations and conventions have been developed. 73 74 Handbook of Algorithms for Physical Design Automation -notation FIGURE Complexity analysis. O -notation -Notation For a function h n h n represents the set of all functions that satisfy the following h n f n there exist positive constants c1 and c2 .
