IEICE TRANSACTIONS on Information
Constant Time Enumeration of Subtrees with Exactly k Nodes in a Tree
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E97-D No.3 pp.421-430
- Publication Date
- 2014/03/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E97.D.421
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science —New Trends in Theory of Computation and Algorithm—)
- Category
- Graph Algorithms, Knowledge Discovery
Authors
Kunihiro WASA
Hokkaido University
Yusaku KANETA
Hokkaido University
Takeaki UNO
National Institute of Informatics
Hiroki ARIMURA
Hokkaido University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kunihiro WASA, Yusaku KANETA, Takeaki UNO, Hiroki ARIMURA, "Constant Time Enumeration of Subtrees with Exactly k Nodes in a Tree" in IEICE TRANSACTIONS on Information,
vol. E97-D, no. 3, pp. 421-430, March 2014, doi: 10.1587/transinf.E97.D.421.
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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E97.D.421/_p
Copy
@ARTICLE{e97-d_3_421,
author={Kunihiro WASA, Yusaku KANETA, Takeaki UNO, Hiroki ARIMURA, },
journal={IEICE TRANSACTIONS on Information},
title={Constant Time Enumeration of Subtrees with Exactly k Nodes in a Tree},
year={2014},
volume={E97-D},
number={3},
pages={421-430},
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.},
keywords={},
doi={10.1587/transinf.E97.D.421},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Constant Time Enumeration of Subtrees with Exactly k Nodes in a Tree
T2 - IEICE TRANSACTIONS on Information
SP - 421
EP - 430
AU - Kunihiro WASA
AU - Yusaku KANETA
AU - Takeaki UNO
AU - Hiroki ARIMURA
PY - 2014
DO - 10.1587/transinf.E97.D.421
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E97-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2014
AB - 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.
ER -
English
