| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 431607 | Journal of Discrete Algorithms | 2015 | 8 Pages |
Abstract
Given two ordered labeled trees P and T, the constrained tree inclusion problem is to determine whether it is possible to obtain P from T through a sequence of deleting degree-one or degree-two nodes. Valiente proposed a bottom up algorithm which solves the problem in O(nPnT)O(nPnT) time and O(nPnT)O(nPnT) space, where nPnP and nTnT are the numbers of the nodes in P and T respectively. In this paper we present a top down matching algorithm which solves the problem in O(nPnT)O(nPnT) time but uses only O(nP+nT)O(nP+nT) space.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yu-Hsiang Hsiao, Keh-Ning Chang,