A simple optimal binary representation of mosaic floorplans and Baxter permutations

作者：He Bryan Dawei^*

来源：Theoretical Computer Science, 2014, 532: 40-50.

DOI：10.1016/j.tcs.2013.05.007

• Floorplan
• Mosaic floorplan
• Baxter permutation
• Binary representation

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).

• 出版日期2014-5-1