Tree inclusion problems
Patrick Cégielski; Irène Guessarian; Yuri Matiyasevich
RAIRO - Theoretical Informatics and Applications (2008)
- Volume: 42, Issue: 1, page 5-20
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topCégielski, Patrick, Guessarian, Irène, and Matiyasevich, Yuri. "Tree inclusion problems." RAIRO - Theoretical Informatics and Applications 42.1 (2008): 5-20. <http://eudml.org/doc/250322>.
@article{Cégielski2008,
abstract = {
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(|T|22|P|) where |T| (resp. |P|) is the size of T (resp. P).
},
author = {Cégielski, Patrick, Guessarian, Irène, Matiyasevich, Yuri},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Subtree inclusion; algorithm; window embedded subtree problems},
language = {eng},
month = {1},
number = {1},
pages = {5-20},
publisher = {EDP Sciences},
title = {Tree inclusion problems},
url = {http://eudml.org/doc/250322},
volume = {42},
year = {2008},
}
TY - JOUR
AU - Cégielski, Patrick
AU - Guessarian, Irène
AU - Matiyasevich, Yuri
TI - Tree inclusion problems
JO - RAIRO - Theoretical Informatics and Applications
DA - 2008/1//
PB - EDP Sciences
VL - 42
IS - 1
SP - 5
EP - 20
AB -
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(|T|22|P|) where |T| (resp. |P|) is the size of T (resp. P).
LA - eng
KW - Subtree inclusion; algorithm; window embedded subtree problems
UR - http://eudml.org/doc/250322
ER -
References
top- L. Boasson, P. Cegielski, I. Guessarian and Yu. Matiyasevich, Window accumulated subsequence matching is linear. Ann. Pure Appl. Logic113 (2001) 59–80.
- Y. Chi, R. Muntz, S. Nijssen and J. Kok, Frequent subtree mining – an overview. Fund. Inform.66 (2005) 161–198.
- P. Kilpelainen, Tree matching problems with applications to structured text databases. Ph.D. thesis, Helsinki (1992). URIhttp://ethesis.helsinki.fi/julkaisut/mat/tieto/vk/kilpelainen/
- P. Kilpelainen and H. Mannila, Ordered and unordered tree inclusion. SIAM J. Comput.24 (1995) 340–356.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.