Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2010-006 (March 05, 2010)

Constant Time Generation of Trees with Degree Bounds
by Bingbing Zhuang and Hiroshi Nagamochi

pdf File

Given a number $n$ of vertices, a lower bound $d$ on the diameter, and a capacity function $\Delta(k)\geq 2$, $k=0,1,\ldots,\lfloor n/2\rfloor$, we consider the problem of enumerating all unrooted trees $T$ with exactly $n$ vertices and a diameter at least $d$ such that the degree of each vertex with distance $k$ from the center of $T$ is at most $\Delta(k)$. We give an algorithm that generates all such trees without duplication in $O(1)$-time delay per output in the worst case using $O(n)$ space. For example, our result implies that all alkanes, structural isomers of chemical graph ${\tt C}_n{\tt H}_{2n+2}$ can be generated in $O(1)$-time delay without duplication.