Document RAIRO-Theor. Inf. Appl. 42, 5-20 (2008)
DOI: 10.1051/ita:2007052
Tree inclusion problems
Patrick Cégielski1, Irène Guessarian2 and Yuri Matiyasevich31 LACL EA 4213, Université Paris Est, Route forestière Hurtault, 77300 Fontainebleau, France; cegielski@univ-paris12.fr
2 LIAFA, UMR 7089 and Université Paris 6, 2 place Jussieu, 75254 Paris Cedex 5, France; ig@liafa.jussieu.fr
3 Steklov Institute of Mathematics, Fontanka 27, St. Petersburg, 191023, Russia; yumat@pdmi.ras.ru
(Published online: 18 January 2008)
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).
Mathematics Subject Classification. 68Q25, 68W05
Key words: Subtree inclusion -- algorithm
© EDP Sciences 2007