Efficient generation of rectangulations and elimination trees via permutation languages

-- Arturo Merino (Technische Universität Berlin)

Time: 15:00 -- Location: online

In this talk we apply the Hartung-Hoang-Mütze-Williams permutation language framework to derive exhaustive generation algorithms for two further classes of combinatorial objects, as well as Hamilton paths and cycles on the corresponding polytopes: (3) different classes of rectangulations, which are subdivisions of a rectangle into smaller rectangles (see www.combos.org/rect); (4) elimination trees of chordal graphs, which encode several interesting combinatorial objects such as permutations, binary trees and bitstrings (see www.combos.org/elim). This talk is based on joint work with Torsten Mütze and Jean Cardinal (SoCG 2021 + SODA 2022).

Category: seminars
Tags: Combi seminar combinatorics