Computer Science – Discrete Mathematics
Scientific paper
2011-12-06
Computer Science
Discrete Mathematics
33 pages, 13 figures
Scientific paper
A floorplan is a rectangular dissection which describes the relative placement of electronic modules on the chip. It is called a mosaic floorplan if there are no empty rooms or cross junctions in the rectangular dissection. We study a subclass of mosaic floorplans called hierarchical floorplans of order $k$ (abbreviated HFO-${k}$). A floorplan is HFO-$k$ if it can be obtained by starting with a single rectangle and recursively embedding mosaic floorplans of at most $k$ rooms inside the rooms of intermediate floorplans. When $k=2$ this is exactly the class of slicing floorplans as the only distinct floorplans with two rooms are a room with a vertical slice and a room with a horizontal slice respectdeively. And embedding such a room is equivalent to slicing the parent room vertically/horizontally. In this paper we characterize permutations corresponding to the Abe-labeling of HFO-$k$ floorplans and also give an algorithm for identification of such permutations in linear time for any particular $k$. We give a recurrence relation for exact number of HFO-5 floorplans with $n$ rooms which can be easily extended to any $k$ also. Based on this recurrence we provide a polynomial time algorithm to generate the number of HFO-$k$ floorplans with $n$ rooms. Considering its application in VLSI design we also give moves on HFO-$k$ family of permutations for combinatorial optimization using simulated annealing etc. We also explore some interesting properties of Baxter permutations which have a bijective correspondence with mosaic floorplans.
Balachandran Shankar
Koroth Sajin
No associations
LandOfFree
A Study on Hierarchical Floorplans of Order k does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Study on Hierarchical Floorplans of Order k, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Study on Hierarchical Floorplans of Order k will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-593637