請用此 Handle URI 來引用此文件: 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
摘要: 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
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。