DocumentCode
1970039
Title
Faster optimal single-row placement with fixed ordering
Author
Brenner, U. ; Vygen, J.
Author_Institution
Res. Inst. for Discrete Math., Bonn Univ., Germany
fYear
2000
fDate
2000
Firstpage
117
Lastpage
121
Abstract
We consider the problem of placing a set of cells in a single row with a given horizontal ordering, minimizing the (weighted) bounding box netlength. We analyze the running time of an algorithm of Kahng, Tucker and Zelikovsky which solves this problem optimally. By using different data structures we are able to improve the worst-case running time in the unweighted case as well as in the presence of netweights
Keywords
logic CAD; minimisation of switching nets; bounding box netlength minimization; clumping algorithm; net weight; one-dimensional placement problem; optimization; ordered single row problem; running time; Algorithm design and analysis; Data structures;
fLanguage
English
Publisher
ieee
Conference_Titel
Design, Automation and Test in Europe Conference and Exhibition 2000. Proceedings
Conference_Location
Paris
Print_ISBN
0-7695-0537-6
Type
conf
DOI
10.1109/DATE.2000.840026
Filename
840026
Link To Document