A bijection between permutations and floorplans, and its applications. (English) Zbl 1096.05002
Summary: A floorplan represents the relative relations between modules on an integrated circuit. Floorplans are commonly classified as slicing, mosaic, or general. Separable and Baxter permutations are classes of permutations that can be defined in terms of forbidden subsequences. It is known that the number of slicing floorplans equals the number of separable permutations and that the number of mosaic floorplans equals the number of Baxter permutations [B. Yao, H. Chen, C.K. Cheng, and R.L. Graham, Floorplan representations: complexity and connections, ACM Trans. Design Automation Electron. Systems 8, 55–80 (2003)]. We present a simple and efficient bijection between Baxter permutations and mosaic floorplans with applications to integrated circuits design. Moreover, this bijection has two additional merits: (1) It also maps between separable permutations and slicing floorplans; and (2) it suggests enumerations of mosaic floorplans according to various structural parameters.
MSC:
| 05A05 | Permutations, words, matrices |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Ackerman, E.; Barequet, G.; Pinter, R. Y., On the number of rectangular partitions, (Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA (2004)), 729-738 |
| [2] | Avis, D.; Newborn, M., On pop-stacks in series, Util. Math., 19, 129-140 (1981) · Zbl 0461.68060 |
| [3] | Baxter, G., On fixed points of the composite of commuting functions, Proc. Amer. Math. Soc., 15, 851-855 (1964) · Zbl 0126.38701 |
| [4] | Bose, P.; Buss, J. F.; Lubiw, A., Pattern matching for permutations, Inform. Process. Lett., 65, 277-283 (1998) · Zbl 1338.68304 |
| [5] | Chung, F. R.K.; Graham, R. L.; Hoggatt, V. E.; Kleiman, M., The number of Baxter permutations, J. Combin. Theory, Ser. A, 24, 382-394 (1978) · Zbl 0398.05003 |
| [6] | Dulucq, S.; Guibert, O., Baxter permutations, Discrete Math., 180, 143-156 (1998) · Zbl 0895.05002 |
| [7] | Hong, X.; Huang, G.; Cai, Y.; Gu, J.; Dong, S.; Cheng, C. K.; Gu, J., Corner block listan effective and efficient topological representation of non-slicing floorplan, (Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, San Jose, CA (2000)), 8-12 |
| [8] | Y. Kajitani, The single sequence that unifies placement and floorplanning, Presented at the First Conference for Asia Universities on Semiconductors Design, 2003.; Y. Kajitani, The single sequence that unifies placement and floorplanning, Presented at the First Conference for Asia Universities on Semiconductors Design, 2003. |
| [9] | Mallows, C. L., Baxter permutations rise again, J. Combin. Theory, Ser. A, 27, 394-396 (1979) · Zbl 0427.05005 |
| [10] | Murata, H.; Fujiyoshi, K.; Nakatake, S.; Kajitani, Y., VLSI module placement based on rectangle-packing by the sequence-pair, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 15, 12, 1518-1524 (1996) |
| [11] | Murata, H.; Fujiyoshi, K.; Watanabe, T.; Kajitani, Y., A mapping from sequence-pair to rectangular dissection, (Proceedings of Asia and South Pacific Design Automation Conference. Proceedings of Asia and South Pacific Design Automation Conference, Chiba, Japan (1997)), 625-633 |
| [12] | Sakanushi, K.; Kajitani, Y.; Mehta, D. P., The quarter-state-sequence floorplan representation, IEEE Trans. on Circuits and Systems I: Fundamental Theory and Applications, 50, 3, 376-386 (2003) · Zbl 1368.68271 |
| [13] | Shapiro, L.; Stephens, A. B., Bootstrap percolation, the Schröder numbers, and the \(N\)-Kings problem, SIAM J. Discrete Math., 4, 275-280 (1991) · Zbl 0736.05008 |
| [14] | Shen, Z. C.; Chu, C. C.N., Bounds on the number of slicing, mosaic, and general floorplans, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 22, 10, 1354-1361 (2003) |
| [15] | R.P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge, 1999.; R.P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge, 1999. · Zbl 0928.05001 |
| [16] | West, J., Generating trees and the Catalan and Schröder numbers, Discrete Math., 146, 247-262 (1995) · Zbl 0841.05002 |
| [17] | Yao, B.; Chen, H.; Cheng, C. K.; Graham, R. L., Floorplan representations: complexity and connections, ACM Transactions on Design Automation of Electronic Systems, 8, 1, 55-80 (2003) |
| [18] | Young, E. F.Y.; Chu, C. C.N.; Shen, C., Twin binary sequences: a non-redundant representation for general non-slicing floorplan, IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 22, 4, 457-469 (2003) |
| [19] | Zhang, X.; Kajitani, Y., Space-planningplacement of modules with controlled empty area by single-sequence, (Proceedings of Asia and South Pacific Design Automation Conference. Proceedings of Asia and South Pacific Design Automation Conference, Yokohama, Japan (2004)), 25-30 |
| [20] | Zhang, X.; Kajitani, Y., A normalized configuration of floorplans and ABLR-relations, (International Conference on Communications, Circuits and Systems. International Conference on Communications, Circuits and Systems, Chengdu, China (2004)), 1218-1222 |
| [21] | Zhang, X.; Kajitani, Y., Theory of T-junction floorplans in terms of single-sequence, (IEEE International Symposium on Circuits and Systems. IEEE International Symposium on Circuits and Systems, Vancouver, Canada (2004)), 341-344 |
| [22] | Zhu, X.; Zhuang, C.; Kajitani, Y., A general packing algorithm based on single-sequence, (International Conference on Communications, Circuits and Systems. International Conference on Communications, Circuits and Systems, Chengdu, China (2004)), 1257-1261 |
| [23] | Zhuang, C.; Zhu, X.; Takashima, Y.; Nakatake, S.; Kajitani, Y., An algorithm for checking slicing floorplan based on HPG and its application, (International Conference on Communications, Circuits and Systems. International Conference on Communications, Circuits and Systems, Chengdu, China (2004)), 1223-1227 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
