AbstractWe present a cost-optimal parallel algorithm for generating t-ary trees. Using a known inversion table representation, our algorithm generates all tree sequences in lexicographic order. It uses a linear array of n processors (where n is the number of nodes in the tree), each having a constant number of registers (each storing an integer of size at most tn), and each being responsible for producing one element of a given tree sequence.
Categories and Subject Descriptors: G.1.0 [Numerical Analysis]; G.2.1 [Discrete Mathematics]: Combinatorics; G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: binary tree, t-ary tree, parallel algorithms, breadth first search, linear array of processors, parallel random access machine, lexicographic order
Selected papers that cite this one
- Bette Bultena and Frank Ruskey. An Eades-KcKay algorithm for well-formed parentheses strings. Information Processing Letters, 68(5):255-259, 15 December 1998.
Selected references
- U. I. Gupta, D. T. Lee, and C. K. Wong. Ranking and unranking of B-trees. Journal of Algorithms, 4(1):51-60, March 1983.
- C. C. Lee, D. T. Lee, and C. K. Wong. Generating binary trees of bounded height. Acta Informatica, 23(5):529-544, 1986.
- Liwu Li. Ranking and unranking of AVL-trees. SIAM Journal on Computing, 15(4):1025-1035, November 1986.
- Joan M. Lucas, D. Roelants van Baronaigien, and Frank Ruskey. On rotations and the generation of binary trees. Journal of Algorithms, 15(3):343-366, November 1993.
- Andrzej Proskurowski. On the generation of binary trees. Journal of the ACM, 27(1):1-2, January 1980.
- Frank Ruskey. Generating t-ary trees lexicographically. SIAM Journal on Computing, 7(4):424-439, November 1978.
- W{\l}adys{\l}aw Skarbek. Generating ordered trees. Theoretical Computer Science, 57(1):153-159, April 1988.
- Anthony E. Trojanowski. Ranking and listing algorithms for k-ary trees. SIAM Journal on Computing, 7(4):492-509, November 1978.
- Robert Alan Wright, Bruce Richmond, Andrew Odlyzko, and Brendan D. McKay. Constant time generation of free trees. SIAM Journal on Computing, 15(2):540-548, May 1986.
- S. Zaks. Lexicographic generation of ordered trees. Theoretical Computer Science, 10(1):63-82, January 1980.
- S. Zaks and D. Richards. Generating trees and other combinatorial objects lexicographically. SIAM Journal on Computing, 8(1):73-81, February 1979.