Fast algorithms to generate open meandric systems and open meanders |
Posted on:2009-01-05 | Degree:M.Sc | Type:Thesis |
University:University of Guelph (Canada) | Candidate:Li, Yue | Full Text:PDF |
GTID:2448390002991492 | Subject:Computer Science |
Abstract/Summary: | |
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. |
Keywords/Search Tags: | Open meander, Open meandric systems, Generate, Constant amortized time, Algorithm |
|
Related items |