Listing and Counting Subtrees of a Tree
Department of Computer Science,
University of Victoria, Canada.
Given an ordered tree T, an ordering is defined on the set
of subtrees of T.
Algorithms are presented for listing all subtrees in that order,
and for determining the tree occupying a given position in the list.
The second algorithm runs in time proportional to the number of vertices
in the tree.
An explicit formula is given for the total number of subtrees summed over
all trees T.
Stephan G. Wagner,
Subset Counting in Trees,
Ars Combinatoria, 89 (2008) 127-139.
Elmar Teufl and Stephan Wagner,
Enumeration Problems for Classes of Self-Similar Graphs,
Journal of Combinatorial Theory, Series A.
114 (2007) 1254-1277.
Ideals In A Forest, One-Way Infinite Binary Trees And The
In ``Mathematics and Computer Science, II (Versailles, 2002),
Trends in Mathematics, Pages 393-414.
Birkhauser, Basel, 2002.
Michel Habib, Raoul Medina, Lhouari Nourine, and George Steiner,
Efficient Algorithms on Distributive Lattices,
Discrete Applied Mathematics, 110 (2001) 169-187.
V Kvasnicka, J Pospichal,
Simple Construction of Embedding Frequencies of Trees and Rooted Trees,
Journal of Chemical Information and Computer Sciences,
35 (1995) 121-128.
Hosam M. Mahmoud,
Evolution of random search trees,
Wiley, New York, 1992, 324 pp., ISBN 0-471-53228-2.
A Survey on Binary Tree Codings,
The Computer Journal, 34 (1991) 438-443.
Carl E. Langenhop and William E. Wright,
A model of the dynamic behavior of B-trees,
Acta Informatica, 27 (1989) 41-59.
Back to list of publications.