Approximation Algorithms for Bus Routing on Printed Circuit Boards

Please enable javascript in your browser.

This page was sent successfuly

Bookmark

1070 viewed

الگوریتم های تقریبی برای مسیریابی گذرگاه ها روی صفحات مدار چاپی

1791 Viewed

Type of Document: M.Sc. Thesis
Language: Farsi
Document No: 55271 (19)
University: Sharif University of Technology
Department: Computer Engineering
Advisor(s): Zarrabizadeh, Hamid
Abstract:
Since the amount of data is increasing, it is important to reduce the size of components and circuits. For instance, bus routing problem, rectangle scape problem, and minimizing number of layers are important problems in printed circuit boards. Rectangle scape problem can be used as an estimation for minimizing number of layers problem. To minimize number of layers in this problem, we are given some axis-parallel rectangles inside a axis-parallel rectangular region. The objective is to extend one of the four boundaries of each rectangle in a certain direction such that all rectangles can be placed without any conflict in minimum number of layers. In this thesis, we analyze a common greedy algorithm for minimizing number of layers problem in which we place the maximum number of possible rectangles in a layer at each step. We show that the approximation factor of this greedy algorithm is at most ln n for each input of n rectangles. We also prove that the approximation factor of this algorithm is at least 1/2 ln n. In the end, we provide an algorithm with constant approximation factor for minimizing number of layers problem
Keywords:
Bus Routing ; Minimization Number of Layers ; Approximate Algorithm ; Printed Circuit Board ; Rectangle Escape Problem

مقدمه
- تعریف مسئله
- اهداف تحقیق
- ساختار پایان‌نامه
مفاهیم اولیه
- مسائل NP
  - بزرگ‌ترین خوشه گراف
  - مسئله‌ی 3-صدق‌پذیری
  - مسئله‌های ان‌پی-سخت
- الگوریتم‌های تقریبی
  - برنامه‌ریزی خطی
کارهای پیشین
- مسئله‌ی فرار مستطیل‌ها
  - کاهش مسئله‌ی 3-SAT به مسئله‌ی فرار مستطیل‌ها
  - الگوریتم‌های تقریبی برای مسئله‌ی فرار مستطیل‌ها
- مسئله بزرگ‌ترین مجموعه مستطیل‌های مجزای مرزی
  - مسئله مسیردهی مجزای بزرگ‌ترین مجموعه مستطیل‌ها
نتایج جدید
- الگوریتم لایه‌بندی کمینه
- تحلیل الگوریتم لایه‌بندی کمینه
- الگوریتم ضریب تقریب ثابت
  - الگوریتم لایه‌بندی کمینه با ضریب تقریب ثابت ۱۶
جمع‌بندی
- کارهای آتی