The Advantages of Forward Thinking in Generating Rooted and Free Trees

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 ACM-SIAM Symposium on Discrete Algorithms (SODA), (1999) S939-940.
• 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.

• Jiexun Wang, Liang Zhao, Hiroshi Nagamochi, and Tatsuya Akutsu, An Efficient Algorithm for Generating Colored Outerplanar Graphs, Lecture Notes in Computer Science, 4484 (2007) 573-583.
• James Korsh and Paul LaFollette, A Loopless Gray Code for Rooted Trees, ACM Transactions on Algorithms, 2 (2006) 135--152.
• Adam Young and Moti Yung, Backdoor Attacks on Black-Box Ciphers Exploiting Low-Entropy 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
• Shin-ichiro Kawano and Shin-ichi Nakano, Generating All Series-Parallel Graphs, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2005 E88-A(5), 1129 - 1135.
• Akimitsu Ono and Shin-ichi 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 Laurent-Varin, Computation of order conditions for symplectic partitioned Runge-Kutta schemes with application to optimal control, Numerische Mathematik, 103 (2005) 1-10.
• Mojtaba Hosseini and Nicolas D. Georganasa, End System Multicast routing for multi-party videoconferencing applications, Computer Communications, 29 (2006) 2046-2065.
• Ping Zhu and Richard C. Wilson, A Study of Graph Spectra for Comparing Graphs, British Machine Vision Conference, Oxford, September 2005.