0000000000451765
AUTHOR
Jean Pallo
Ranking and unrankingk-ary trees with a 4k –4 letter alphabet
Abstract The problem of the direct generation in A-order of binary trees was stated by Zaks in 1980. In 1988 Roelants van Baronaigien and Ruskey gave a solution for k-ary trees with n internal nodes using an encoding sequence of kn+1 integers between 1 and n. Vajnovszki and Pallo improved this result for binary trees in 1994 using words of length n–1 on a four letter alphabet. Recently Korsh generalized the Vajnovszki and Pallo’s generating algorithm to k-ary trees using an alphabet whose cardinality depends on k but not on n. We give in this paper ranking and unranking algorithms for k-ary trees using the Korsh’s encoding scheme.
Two shortest path metrics on well-formed parentheses strings
We present an analysis of two transformations on well-formed parentheses strings. Using a lattice approach, the corresponding least-move distances are computable, the first in linear time and the second in quadratic time.
A simple algorithm for generating neuronal dendritic trees
Abstract A simple, efficient algorithm is presented for generating the codewords of all neuronal dendritic trees with a given number of terminal nodes. Furthermore, a procedure is developed for deciding if different codewords correspond to topologically equivalent trees.
Generating binary trees by Glivenko classes on Tamari lattices
Using algebraic-theoretic results, we give an algorithm for generating binary trees within Glivenko classes in Tamari lattices. Tamari lattices are lattices of binary trees endowed by the well-known rotation transformation.