Subclasses of Baxter permutations based on pattern avoidance

DOI10.1007/978-3-319-34171-2_14MaRDI QIDQ5740186zbMATH OpenOpenAlexFDO

Authors Shankar Balachandran, Sajin Koroth

Publication date 25 July 2016

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.1374

zbMATH Keywords

Baxter permutationfloorplanningpattern avoidance

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Abstract: Baxter permutations are a class of permutations which are in bijection with a class of floorplans that arise in chip design called mosaic floorplans. We study a subclass of mosaic floorplans called $HF{O}_k$ defined from mosaic floorplans by placing certain geometric restrictions. This naturally leads to studying a subclass of Baxter permutations. This subclass of Baxter permutations are characterized by pattern avoidance. We establish a bijection, between the subclass of floorplans we study and a subclass of Baxter permutations, based on the analogy between decomposition of a floorplan into smaller blocks and block decomposition of permutations. Apart from the characterization, we also answer combinatorial questions on these classes. We give an algebraic generating function (but without a closed form solution) for the number of permutations, an exponential lower bound on growth rate, and a linear time algorithm for deciding membership in each subclass. Based on the recurrence relation describing the class, we also give a polynomial time algorithm for enumeration. We finally prove that Baxter permutations are closed under inverse based on an argument inspired from the geometry of the corresponding mosaic floorplans. This proof also establishes that the subclass of Baxter permutations we study are also closed under inverse. Characterizing permutations instead of the corresponding floorplans can be helpful in reasoning about the solution space and in designing efficient algorithms for floorplanning.

Recommendations

• A bijection between permutations and floorplans, and its applications
• Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations
• A simple optimal binary representation of mosaic floorplans and Baxter permutations
• Baxter permutations and plane bipolar orientations
• Baxter permutations and plane bipolar orientations

Cites work

• A bijection between permutations and floorplans, and its applications
• Fast recognition of Baxter permutations using syntactical and complete bipartite composite dag's
• Optimal orientations of cells in slicing floorplan designs
• Simple permutations and pattern restricted permutations
• The Hopf algebra of diagonal rectangulations.
• Trees, slices, and wheels: On the floorplan area minimization problem

Cited in

(5)

• Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations
• A simple optimal binary representation of mosaic floorplans and Baxter permutations
• A bijection between permutations and floorplans, and its applications
• Optimal binary representation of mosaic floorplans and Baxter permutations
• On the sub-permutations of pattern avoiding permutations

This page was built for publication: Subclasses of Baxter permutations based on pattern avoidance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5740186)