| 摘要 | 第1-5页 |
| Abstract | 第5-9页 |
| 1 VLSI physical design automation | 第9-17页 |
| ·The VLSI design process | 第9-11页 |
| ·Physical design | 第11-13页 |
| ·Routing | 第13-14页 |
| ·Cost functions and constraints | 第14-17页 |
| 2 Rectilinear Steiner tree problem | 第17-25页 |
| ·Introduction | 第17-19页 |
| ·Basic definitions and problem formulation | 第19-20页 |
| ·Overview of results | 第20-22页 |
| ·Approximation algorithms | 第22-24页 |
| ·Main task of this thesis | 第24-25页 |
| 3 Minimum convex polygon | 第25-37页 |
| ·The Hanan grid | 第25-26页 |
| ·The minimum convex polygon | 第26-37页 |
| 4 Weighted Lee algorithm | 第37-45页 |
| ·Maze routing algorithms | 第37-38页 |
| ·Lee algorithm | 第38-39页 |
| ·Weighted Lee algorithm | 第39-45页 |
| 5 Quality of solution | 第45-49页 |
| ·Time complexity analysis | 第45-46页 |
| ·Performance ratio | 第46页 |
| ·The Steiner ratio | 第46-49页 |
| 6 RSMT in higher-dimensional space | 第49-59页 |
| ·Multi-layer routing | 第49-52页 |
| ·RSMT in 3-dimensional space | 第52-56页 |
| ·RSMT in higher-dimensional space | 第56-59页 |
| 7 Conclusions and extensions | 第59-61页 |
| Bibliography | 第61-65页 |
| 致谢 | 第65-67页 |
| 个人简介 | 第67-68页 |
