Generalized terminal connectivity problem for multilayer layout scheme
Journal
Computer-Aided Design
Journal Volume
22
Journal Issue
7
Pages
423-433
Date Issued
1990
Author(s)
Abstract
Given a set of n horizontal (or vertical) wire segments run on different layers with variable widths (or heights), and a set of m terminals placed on different layers and with arbitrary rectangular shapes, a generalization of the terminal connectivity problem (TCP) is considered. This TCP can be applied to facilitate the VLSI or PCB multi-layer layout. First, it is proved that this TCP is NP-hard by showing that it is equivalent to a minimal steiner tree problem, which has been proved NP-complete. Then an efficient algorithm for the TCP is presented which runs in O(m + (1 + c)nn) time (with some preprocessing work). Experimental results are given to verify the effectiveness of the algorithm. © 1990.
Subjects
electronic design automation; hyper-complete graph; minimal steiner tree; shortest connectivity path; terminal connectivity
Other Subjects
Computer Programming--Algorithms; Integrated Circuits--Layout; Printed Circuits; Electronic Design Automation; Hyper-Complete Graph; Minimal Steiner Tree; Multilayer Layout; Terminal Connectivity; Electronic Circuits
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
02.pdf
Size
1.1 MB
Format
Adobe PDF
Checksum
(MD5):c1c6e9f601e061bd33aa81db3d613d7f