The Advantages of Forward Thinking in Generating Rooted and Free Trees
Gang Li,
Department of Computer Science,
University of Victoria, Canada.
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
We present a new approach to the exhaustive generation of rooted and
free trees of n nodes.
Our algorithms have the following features:
(1) They are optimal in the sense of using linear space and
having running times that are proportional to the number of trees
produced.
(2) They use a natural representation of the trees, the parent array.
(3) They can generate the trees in many different orders, including
reverse lexicographic order.
(4) They are recursive, not iterative.
(5) They can be easily modified to generate restricted classes of trees and
still preserve properties (1)(4).
The possible restrictions are: (a) in the case of rooted trees,
upper bounds on the number of
children of a node and lower and upper bounds on the height of the tree;
and (b) in the case of free trees, upper bounds on the degree of a node and
lower and upper bounds on the diameter of the tree.

The postscript file is 216,838 bytes,
the dvi file is 32,888 bytes.
Please send me a note
if you download a copy  Thanks!

Presented at the
10th Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), (1999) S939940.

The algorithms have been implemented and are used as the basis of
some of the online tree generation algorithms of
COS,
the Combinatorial Object Server, in the section on
generating
trees.

Gang (Kenny) Li now works for IBM Research Labs in Toronto.
Selected publications that refer to this paper:

Jiexun Wang, Liang Zhao, Hiroshi Nagamochi,
and Tatsuya Akutsu,
An Efficient Algorithm for Generating Colored Outerplanar Graphs,
Lecture Notes in Computer Science, 4484 (2007) 573583.

James Korsh and Paul LaFollette,
A Loopless Gray Code for Rooted Trees,
ACM Transactions on Algorithms, 2 (2006) 135152.

Adam Young and Moti Yung,
Backdoor Attacks on BlackBox Ciphers Exploiting
LowEntropy Plaintexts,
Lecture Notes in Computer Science 2727, 2003, pp. 297  311.
Information Security and Privacy: 8th Australasian Conference,
ACISP 2003 Wollongong, Australia.

Brice Effantin,
Generation of Unordered Binary Trees,
Lecture Notes in Computer Science 3045, 2004, pp. 648  655.
Computational Science and Its Applications  ICCSA 2004:
International Conference, Assisi, Italy

Shinichiro Kawano and Shinichi Nakano,
Generating All SeriesParallel Graphs,
IEICE Transactions on Fundamentals of Electronics,
Communications and Computer Sciences, 2005 E88A(5), 1129  1135.

Akimitsu Ono and Shinichi Nakano,
Constant Time Generation of Linear Extensions,
Lecture Notes in Computer Science 3623, 2005, pp. 445  ???.
Fundamentals of Computation Theory: 15th International Symposium,
FCT 2005, Lübeck, Germany

Stephane Coulomb,
Minimal vertex covers of random trees,
Journal of Statistical Mechanics: Theory and Experiment,
(2005) P06007, 9 pages.

Bart Goethals, Eveline Hoekx, and Jan Van den Bussche,
Mining Tree Queries in a Graph,
11th ACM SIGKDD International Conference on Knowledge Discovery
and Data Mining (KDD), 2005.

J. Frédéric Bonnans1 and Julien LaurentVarin,
Computation of order conditions for symplectic partitioned
RungeKutta schemes with application to optimal control,
Numerische Mathematik, 103 (2005) 110.

Mojtaba Hosseini and Nicolas D. Georganasa,
End System Multicast routing for multiparty videoconferencing
applications, Computer Communications,
29 (2006) 20462065.

Ping Zhu and Richard C. Wilson,
A Study of Graph Spectra for Comparing Graphs,
British Machine Vision Conference,
Oxford, September 2005.
Back to list of publications.