Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Tuesday, June 28, 2022, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Arturo Merino (TU Berlin)

Efficient generation of rectangulations via permutation languages

Recently, Hartung, Hoang, Mütze and Williams (SODA 2020) presented a versatile algorithmic framework for exhaustively generating a large variety of combinatorial objects, based on encoding them as permutations. In this talk we recap the basics of this framework, and we present a new application of it. Another application will be discussed in the Mittagsseminar talk on Thursday. Specifically, we derive exhaustive generation algorithms for various classes of rectangulations, which are subdivisions of a square into rectangles. In particular, these results apply to classes of rectangulations that are characterized by avoiding certain patterns, and we initiate a systematic investigation of pattern avoidance in rectangulations. Our generation algorithms are efficient, in some cases even loopless or constant amortized time, i.e., each new rectangulation is generated in constant time in the worst case or on average, respectively. Moreover, the Gray codes we obtain are cyclic, and sometimes provably optimal, in the sense that they correspond to a Hamilton cycle on the skeleton of an underlying polytope. Implementations of our algorithms are available for experimentation on the Combinatorial Object Server: www.combos.org/rect.

This is joint work with Torsten Mütze (SoCG 2021).

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login