6533b82cfe1ef96bd128e9de
RESEARCH PRODUCT
On the loopless generation of binary tree sequences
Vincent Vajnovszkisubject
Discrete mathematicsAmortized analysisBinary treeLexicographical orderPseudorandom binary sequenceComputer Science ApplicationsTheoretical Computer ScienceGray codeCombinatoricsSignal ProcessingBinary codeInformation SystemsCoding (social sciences)Mathematicsdescription
Weight sequences were introduced by Pallo in 1986 for coding binary trees and he presented a constant amortized time algorithm for their generation in lexicographic order. A year later, Roelants van Baronaigien and Ruskey developed a recursive constant amortized time algorithm for generating Gray code for binary trees in Pallo's representation. It is common practice to find a loopless generating algorithm for a combinatorial object when enunciating a Gray code for this object. In this paper we regard weight sequences as variations and apply a Williamson algorithm in order to obtain a loopless generating algorithm for the Roelants van Baronaigien and Ruskey's Gray code for weight sequences.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1998-11-01 | Information Processing Letters |