Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, July 26, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Takeaki Uno (National Institute of Informatics (NII)
In this talk, we consider several problems of enumerating all (non-isomorphic) trees of at most n vertices, where n is a given input number. We give algorithms for solving the enumeration problems. Each algorithm take O(1) time for each tree to be output, i.e., the running time of the algorithms is linear in the number of trees. The technique the algorithms use is reverse search. We give a parent-child relation for trees so that the relation induces a directed spanning tree (search tree) on the set of trees. Since the parent-child relation is simple and has a good property, we can generate children of a parent tree in O(1) time for each, Thus, to traverse the tree, we take O(1) time for each move, and we can enumerate all the tree in O(1) time for each.
Automatic MiSe System Software Version 1.4803M | admin login