Title :
An Isolated-Subtree Inclusion for Unordered Trees
Author :
Hokazono, Takahiro ; Kan, Tomohiro ; Yamamoto, Yoshiyuki ; Hirata, Kouichi
Author_Institution :
Dept. of Artificial Intell., Kyushu Inst. of Technol., Iizuka, Japan
Abstract :
An unordered tree inclusion is the problem of determining whether or not an unordered tree P is included in an unordered tree T. In this paper, we introduce an isolated-sub tree inclusion by restricting that disjoint sub trees of P are always included in disjoint sub trees of T. Then, we design the algorithm to solve the isolated-sub tree inclusion in O(|T|·|P|1.5) time and in O(|T|·|P|) space.
Keywords :
computational complexity; trees (mathematics); disjoint sub trees; isolated-subtree inclusion; unordered tree inclusion; unordered trees; Informatics; inclusion mapping; isolated-subtree inclusion; unordered tree inclusion;
Conference_Titel :
Advanced Applied Informatics (IIAIAAI), 2012 IIAI International Conference on
Conference_Location :
Fukuoka
Print_ISBN :
978-1-4673-2719-0
DOI :
10.1109/IIAI-AAI.2012.74
