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

Keywords: Information Resources Management / Information Science Reference / Library & Information Science / Library Science

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.

The IRMA Community

Research IRM

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

Purchase

Abstract

Related Content

IRMA Sponsors