An Optimal Algorithm for Layered Wheel Floorplan Designs

dc.contributor.authorBettayeb, Said
dc.date.accessioned2020-05-05T16:44:34Z
dc.date.available2020-05-05T16:44:34Z
dc.date.issued1999
dc.description.abstractIn this paper, we present an efficient algorithm to solve the orientation optimization problem for a layered wheel floorplan. The strategy used is to generate all the nonredundant implementations for the floorplan. The computational complexities of the algorithm depend on the actual dimensions of the cells in the floorplan. In the best case, it takes O(n) time and O(n) space, where n is the number of layers in the floorplan. In the worst case, it takes O(2) time and O(2) space. Furthermore, we prove that the time and space complexities for the worst case are optimal. A set of conditions is obtained to check whether the floorplan belongs to the worst case. Using these conditions, we show that even though the worst case is theoretically unavoidable it is not encountered in practical situations where the cell dimensions are bounded.en_US
dc.identifier.citation• An Optimal Algorithm for Layered Wheel Floorplan Designs, (with P. Kulasinghe), Journal Networks Vol. 34, 1999, pp. 67-72.en_US
dc.identifier.urihttps://hdl.handle.net/10657.1/2326
dc.publisherJournal Networksen_US
dc.subjectAlgorithm Best, worst and average case Optimization problem Mathematical optimization Time complexity Analysis of algorithms Polynomial Computation John D. Wiley Very-large-scale integration Scroll wheelen_US
dc.titleAn Optimal Algorithm for Layered Wheel Floorplan Designsen_US
dc.typeArticleen_US
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
An Optimal Algorithm for Layered Wheel Floorplan Design.pdf
Size:
57.44 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description: