Space efficient algorithms for ordered tree comparison

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

8 Scopus Citations
Scopus Metrics
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)283-297
Journal / PublicationAlgorithmica (New York)
Volume51
Issue number3
Publication statusPublished - Jul 2008

Link(s)

DOI

DOI
Check@CityULib
Link to Scopus https://www.scopus.com/record/display.uri?eid=2-s2.0-43949127388&origin=recordpage
Permanent Link https://scholars.cityu.edu.hk/en/publications/publication(15cc1980-b828-4676-9f2b-222f08125ffe).html

Abstract

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. © 2008 Springer Science+Business Media, LLC.

Research Area(s)

  • Alignment of trees, Constrained tree edit distance, Space efficient algorithms

Fingerprint

Publication fingerprints text

100
Algorithm Mathematics
100
Trees Mathematics
100
Ordered Tree Keyphrases
100
Space-efficient Alg... Keyphrases
100
Tree Comparison Keyphrases
100
algorithms INIS
100
comparative evaluat... INIS
100
space INIS
100
Algorithms Computer Science
100
Efficient Algorithm Computer Science
Full Fingerprint ›

Citation Format(s)

[ RIS ] [ BibTeX ]
Space efficient algorithms for ordered tree comparison. / Wang, Lusheng; Zhang, Kaizhong.
In: Algorithmica (New York), Vol. 51, No. 3, 07.2008, p. 283-297.

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review