The IRMA Community
Newsletters
Research IRM
Click a keyword to search titles using our InfoSci-OnDemand powered search:
|
A Fast and Space-Economical Algorithm for the Tree Inclusion Problem
Abstract
The ordered tree inclusion is an interesting problem, by which the authors will check whether a pattern tree P can be included in a target tree T, where the order of siblings in both P and T is significant. In this chapter, the authors propose an efficient algorithm for this problem. Its time complexity is bounded by O(|T|⋅loghP) with O(|T| + |P|) space being used, where hP represents the height of P. Up to now the best algorithm for this problem needs Θ(|T|⋅|leaves(P)|) time, where leaves(P) stands for the set of the leaves of P.
Related Content
|
Christine Kosmopoulos.
© 2022.
22 pages.
|
|
Melkamu Beyene, Solomon Mekonnen Tekle, Daniel Gelaw Alemneh.
© 2022.
21 pages.
|
|
Rajkumari Sofia Devi, Ch. Ibohal Singh.
© 2022.
21 pages.
|
|
Ida Fajar Priyanto.
© 2022.
16 pages.
|
|
Murtala Ismail Adakawa.
© 2022.
27 pages.
|
|
Shimelis Getu Assefa.
© 2022.
17 pages.
|
|
Angela Y. Ford, Daniel Gelaw Alemneh.
© 2022.
22 pages.
|
|
|