Tree inclusion problems
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 42 (2008) no. 1, pp. 5-20.

Given two trees (a target $T$ and a pattern $P$) and a natural number $w$, window embedded subtree problems consist in deciding whether $P$ occurs as an embedded subtree of $T$ and/or finding the number of size (at most) $w$ windows of $T$ which contain pattern $P$ as an embedded subtree. $P$ is an embedded subtree of $T$ if $P$ can be obtained by deleting some nodes from $T$ (if a node $v$ is deleted, all edges adjacent to $v$ are also deleted, and outgoing edges are replaced by edges going from the parent of $v$ (if it exists) to the children of $v$). Deciding whether $P$ is an embedded subtree of $T$ is known to be NP-complete. Our algorithms run in time $O\left(|T|{2}^{{2}^{|P|}}\right)$ where $|T|$ (resp. $|P|$) is the size of $T$ (resp. $P$).

DOI: 10.1051/ita:2007052
Classification: 68Q25,  68W05
Keywords: subtree inclusion, algorithm
@article{ITA_2008__42_1_5_0,
author = {C\'egielski, Patrick and Guessarian, Ir\ene and Matiyasevich, Yuri},
title = {Tree inclusion problems},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {5--20},
publisher = {EDP-Sciences},
volume = {42},
number = {1},
year = {2008},
doi = {10.1051/ita:2007052},
zbl = {1149.68040},
mrnumber = {2382541},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2007052/}
}
TY  - JOUR
AU  - Cégielski, Patrick
AU  - Guessarian, Irène
AU  - Matiyasevich, Yuri
TI  - Tree inclusion problems
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
DA  - 2008///
SP  - 5
EP  - 20
VL  - 42
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007052/
UR  - https://zbmath.org/?q=an%3A1149.68040
UR  - https://www.ams.org/mathscinet-getitem?mr=2382541
UR  - https://doi.org/10.1051/ita:2007052
DO  - 10.1051/ita:2007052
LA  - en
ID  - ITA_2008__42_1_5_0
ER  - 
%0 Journal Article
%A Cégielski, Patrick
%A Guessarian, Irène
%A Matiyasevich, Yuri
%T Tree inclusion problems
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 5-20
%V 42
%N 1
%I EDP-Sciences
%U https://doi.org/10.1051/ita:2007052
%R 10.1051/ita:2007052
%G en
%F ITA_2008__42_1_5_0
Cégielski, Patrick; Guessarian, Irène; Matiyasevich, Yuri. Tree inclusion problems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 42 (2008) no. 1, pp. 5-20. doi : 10.1051/ita:2007052. http://www.numdam.org/articles/10.1051/ita:2007052/`

[1] L. Boasson, P. Cegielski, I. Guessarian and Yu. Matiyasevich, Window accumulated subsequence matching is linear. Ann. Pure Appl. Logic 113 (2001) 59-80. | MR | Zbl

[2] Y. Chi, R. Muntz, S. Nijssen and J. Kok, Frequent subtree mining - an overview. Fund. Inform. 66 (2005) 161-198. | MR | Zbl

[3] P. Kilpelainen, Tree matching problems with applications to structured text databases. Ph.D. thesis, Helsinki (1992). http://ethesis.helsinki.fi/julkaisut/mat/tieto/vk/kilpelainen/

[4] P. Kilpelainen and H. Mannila, Ordered and unordered tree inclusion. SIAM J. Comput. 24 (1995) 340-356. | MR | Zbl

Cited by Sources: