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

• WASA Kunihiro

  Graduate School of Information Science and Technology, Hokkaido University

• KANETA Yusaku

  Graduate School of Information Science and Technology, Hokkaido University

• UNO Takeaki

  National Institute of Informatics

• 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 k-subtree enumeration problem with a tree of n 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 k-subtrees of an input rooted tree in O(1) worst-case time per subtree. This result improves on the straightforward application of Ferreira et al.'s algorithm with O(k) 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

Keywords

• graph algorithm
• enumeration algorithm
• constant delay enumeration
• motif discovery
• tree mining

Details

• CRID: 1390282679354374528
• NII Article ID: 130003394857
• DOI: 10.1587/transinf.e97.d.421
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E97.D/3/E97.D_421/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed