2010 | OriginalPaper | Chapter
Generating Trees on Multisets
Authors : Bingbing Zhuang, Hiroshi Nagamochi
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a multiset
M
=
V
1
∪
V
2
∪ ⋯ ∪
V
C
of
n
elements and a capacity function Δ: [1,
C
]→[2,
n
− 1], we consider the problem of enumerating all unrooted trees
T
on
M
such that the degree of each vertex
v
∈
V
i
is bounded from above by Δ(
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, with
O
(
n
) initial preprocessing time.