Space Efficient Algorithms for Ordered Tree Comparison | Zendy

Lusheng Wang | Zendy; Kaizhong Zhang | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Space Efficient Algorithms for Ordered Tree Comparison

Author(s) -

Lusheng Wang,

Kaizhong Zhang

Publication year - 2005

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/11602613_39

Subject(s) - computer science , tree (set theory) , algorithm , space (punctuation) , computational complexity theory , theoretical computer science , time complexity , tree structure , mathematics , binary tree , combinatorics , operating system

In this paper we present techniques to significantly improve the space complexity of several ordered tree comparison algorithms without sacrificing the corresponding time complexity. We present new algorithms for computing the constrained ordered tree edit distance and the alignment of (ordered) trees. The techniques can also be applied to other related problems.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research