Constant Time Enumeration of Subtrees with Exactly <i>k</i> Nodes in a Tree

By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the <i>k</i>-subtree enumeration problem with a tree of <i>n</i> nodes as an input graph, which is originally introduced by (Ferreira, Grossi, and Rizzi, ESA'11, 275-286, 2011) for general graphs. Based on reverse search technique (Avis and Fukuda, Discrete Appl. Math., vol.65, pp.21-46, 1996), we present the first constant delay enumeration algorithm that lists all <i>k</i>-subtrees of an input rooted tree in <i>O</i>(1) worst-case time per subtree. This result improves on the straightforward application of Ferreira et al.'s algorithm with <i>O</i>(<i>k</i>) amortized time per subtree when an input is restricted to tree. Finally, we discuss an application of our algorithm to a modification of the graph motif problem for trees.