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

Access this Article

Author(s)

    • WASA Kunihiro
    • Graduate School of Information Science and Technology, Hokkaido University
    • KANETA Yusaku
    • Graduate School of Information Science and Technology, Hokkaido University
    • ARIMURA Hiroki
    • Graduate School of Information Science and Technology, Hokkaido University

Abstract

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.

Journal

  • IEICE Transactions on Information and Systems

    IEICE Transactions on Information and Systems E97.D(3), 421-430, 2014

    The Institute of Electronics, Information and Communication Engineers

Codes

Page Top