Title: Meanders and Stamp Foldings - Fast Generation Algorithms

Meanders, semi-meanders and stamp foldings are combinatorial objects that can all be represented by restricted classes of permutations. Enumeration formulae for these objects, however, are currently unknown and many attempts have been made to bound their growth rate. One approach to enumerate these objects is to develop fast generation algorithms to exhaustively list all non-isomorphic instances for a given order N. Such algorithms are the focus of this talk.

Using a permutation representation, we will introduce a data structure that can be used to efficiently list these objects. In the case of meanders - we apply an optimization to improve the running time. Applying such an optimization, however, makes the analysis a challenge - and illustrates how the enumeration of such objects often plays a critical role in an amortized analysis.