Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/38356
標題: Planar Subset of Multi-terminal Nets
作者: K.F.Liao
D.T.Lee
M.Sarrafzadeh
關鍵字: VLSI layout;planar subset;single-layer routing;algorithmic complexity
出版社: Elsevier Science Publishers B. V. Amsterdam, The Netherlands, The Netherlands
Project: Integration, the VLSI Journal, Volume�10, Issue�1, Page(s) �19-37.
摘要: 
The problem of finding a maximum-weighted planar subset of n multi-terminal nets in a global routing with w modules is considered. When w = 0, an optimal algorithm, running in O(n log n + t) time in bipartite regions (channels) and in O(nt) time in arbitrary regions (switchboxes), is presented; where t is the total number of terminals. For arbitrary w, the problem is shown to be NP-hard. For a fixed w, an O(nw+1t) time algorithm, suitable for regions with small numbers of modules (e.g. a ‘ring’ where w = 1) is presented.
URI: http://hdl.handle.net/11455/38356
ISSN: 0167-9260
DOI: 10.1016/S0167-9260(05)80033-1
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.