Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2010-009 (April 13, 2010)

Generating Trees on Multisets
by Bingbing Zhuang and Hiroshi Nagamochi

pdf File

Given a multiset $M=V_1\cup V_2\cup\cdots\cup V_C$ of $n$ elements and a capacity function $\Delta: [1,C]\rightarrow [2,n-1]$, we consider the problem of enumerating all unrooted trees $T$ on $M$ such that the degree of each vertex $v\in V_i$ is bounded from above by $\Delta(i)$. The problem has a direct application of enumerating isomers of tree-like chemical graphs. 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.