Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2010-009 (April 13, 2010)
Generating Trees on Multisets
by Bingbing Zhuang and Hiroshi Nagamochi
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.