کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
438300 | 690254 | 2014 | 11 صفحه PDF | دانلود رایگان |
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).
Journal: Theoretical Computer Science - Volume 532, 1 May 2014, Pages 40-50