Fast algorithms to generate open meandric systems and open meanders.

摘要

An open meander is a self-avoiding river that crosses an infinite straight road underneath a finite number of bridges. Applications of open meanders include stamp foldings and polymer physics. A generalization of an open meander is an open meandric system which allows multiple open meanders.; In this thesis, we develop two generation algorithms. The first algorithm uses a language representation to generate all open meandric systems of order n in Gray code order. This algorithm runs in constant amortized time. The second algorithm uses a permutation representation to generate all open meanders of order n. We conjecture the running time is also constant amortized time.