IRMA-International.org: Creator of Knowledge
Information Resources Management Association
Advancing the Concepts & Practices of Information Resources Management in Modern Organizations

A Fast and Space-Economical Algorithm for the Tree Inclusion Problem

A Fast and Space-Economical Algorithm for the Tree Inclusion Problem
View Sample PDF
Author(s): Yangjun Chen (University of Winnipeg, Canada) and Yibin Chen (University of Winnipeg, Canada)
Copyright: 2019
Pages: 16
Source title: Advanced Methodologies and Technologies in Library Science, Information Management, and Scholarly Inquiry
Source Author(s)/Editor(s): Mehdi Khosrow-Pour, D.B.A. (Information Resources Management Association, USA)
DOI: 10.4018/978-1-5225-7659-4.ch021

Purchase

View A Fast and Space-Economical Algorithm for the Tree Inclusion Problem on the publisher's website for pricing and purchasing information.

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

Ramakrishnan Ramanathan, Lok Wan Lorraine Ko, Hsin Chen, Usha Ramanathan. © 2020. 12 pages.
Debra N. Weiss-Randall. © 2020. 14 pages.
Jayne Cubbage. © 2020. 18 pages.
Japhet Eke Lawrence. © 2020. 20 pages.
Amir Manzoor. © 2020. 28 pages.
Shantanu Pal. © 2020. 19 pages.
Martha Garcia-Murillo, Moinul Zaber, Marcio Wohlers de Almeida. © 2020. 22 pages.
Body Bottom