A simple optimal binary representation of mosaic floor plans and Baxter permutations
- Creators
- He, Bryan Dawei
Abstract
Mosaic floorplans are rectangular structures subdivided into smaller rectangular sections and are widely used in VLSI circuit design. Baxter permutations are a set of permutations that have been shown to have a one-to-one correspondence to objects in the Baxter combinatorial family, which includes mosaic floorplans. An important problem in this area is to find short binary string representations of the set of n-block mosaic floorplans and Baxter permutations of length n. The best known representation is the Quarter-State Sequence which uses 4n bits. This paper introduces a simple binary representation of n-block mosaic floorplan using 3n−3 bits. It has been shown that any binary representation of n-block mosaic floorplans must use at least (3n−o(n)) bits. Therefore, the representation presented in this paper is optimal (up to an additive lower order term).
Additional Information
© 2013 Elsevier B.V.Attached Files
Submitted - 1111.4937v2.pdf
Files
Name | Size | Download all |
---|---|---|
md5:d3f89d85aeb72be4a997f0e8d55d9ee3
|
294.1 kB | Preview Download |
Additional details
- Eprint ID
- 46248
- Resolver ID
- CaltechAUTHORS:20140612-133033753
- Created
-
2014-06-12Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field