Buch, Englisch, 440 Seiten, Format (B × H): 216 mm x 279 mm, Gewicht: 789 g
Complexity and Algorithms
Buch, Englisch, 440 Seiten, Format (B × H): 216 mm x 279 mm, Gewicht: 789 g
ISBN: 978-0-8493-0931-1
Verlag: Taylor & Francis
This book focuses on computation complexity and design of algorithms for multi-layer channel routing. In particular, it deals with various large-scale, computationally intensive optimization problems that have specific applications in many technology-supported routing models. The author includes numerous examples and exercises along with many hard-copy solutions that illustration the feasibility of different routing solutions. He also mentions several problems that remain open, pointing the way for future research.
Zielgruppe
Postgraduate students, researchers, and people in the computer sciences, particularly design automation, computer-aided design (CAD), and VLSI CAD.
Autoren/Hrsg.
Fachgebiete
Weitere Infos & Material
LITERATURE SURVEYTerminology and DefinitionsTwo- and Three-Layer Routing is NP-CompleteAlgorithms for Channel RoutingRESOLVING HORIZONTAL CONSTRAINTS INMULTI-LAYER CHANNEL ROUTINGAlgorithms for Two-Layer Routing in the Absence of Vertical ConstraintsMulti-Layer Vi+1Hi Channel RoutingA GENERAL FRAMEWORK FOR TRACK ASSIGNMENT IN MULTI-LAYER CHANNEL ROUTINGFormulation of the Problem and the AlgorithmExtensions of the TAH Framework to Other ProblemsCOMPUTATIONAL COMPLEXITY OF WIRE LENGTH MINIMIZATION IN CHANNEL ROUTINGWire Length Minimization in Channel RoutingNP-Completeness Results, Two- and Three-Layer No-Dogleg RoutingNP-Completeness Results in Multi-Layer No-Dogleg RoutingNP- Completeness Results in Multi-Layer Restricted Dogleg RoutingALGORITHMS FOR MINIMIZING WIRE LENGTH IN MULTI-LAYER CHANNEL ROUTINGAlgorithms for Minimizing Wire Length in Vi+1Hi Channel RoutingAlgorithm for Minimizing Wire Length in Two-Layer VH Channel RoutingAlgorithm for Minimizing Wire Length in Three-Layer HVH Channel RoutingNOTE: Overviews/Conclusions begin and end each chapter
