A node-labeled rooted tree
T (with root
r) is an all-or-nothing subtree (called
AoN-subtree) of a node-labeled rooted tree
T′ if (1)
T is a subtree of the tree rooted at some node
u (with the same label as
r) of
T′, (2) for each internal node
v of
T,
all the neighbors of
v in
T′ are the neighbors of
v in
T. Tree
T′ is then called an
AoN-supertree of
T. Given a set
T={T1,T2,¼, Tn}{\mathcal {T}}=\{{T}_1,{T}_2,\cdots, {T}_n\} of
nnode-labeled rooted trees, smallest common AoN-supertree problem seeks the smallest possible
node-labeled rooted tree (denoted as
LCST{\textbf{LCST}}) such that every tree
T
i
in
T{\mathcal {T}} is an
AoN-subtree of
LCST{\textbf{LCST}}. It generalizes the smallest superstring problem and it has applications in glycobiology. We present a polynomial-time greedy
algorithm with approximation ratio 6.