Space efficient algorithms for ordered tree comparison

Lusheng Wang; Kaizhong Zhang

doi:10.1007/11602613_39

Space efficient algorithms for ordered tree comparison

Lusheng Wang
, Kaizhong Zhang

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

1 Citation (Scopus)

Abstract

In this paper we present techniques to significantly improve the space complexity of several ordered tree comparison algorithms with-out 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. © Springer-Verlag Berlin Heidelberg 2005.

Original language	English
Title of host publication	Algorithms and Computation
Subtitle of host publication	16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings
Editors	Xiaotie Deng, Ding-Zhu Du
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	380-391
ISBN (Electronic)	978-3-540-32426-3
ISBN (Print)	9783540309352
DOIs	https://doi.org/10.1007/11602613_39
Publication status	Published - 2005
Event	16th International Symposium on Algorithms and Computation (ISAAC 2005) - Hainan, China Duration: 19 Dec 2005 → 21 Dec 2005

Publication series

Name	Lecture Notes in Computer Science
Volume	3827
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Symposium on Algorithms and Computation (ISAAC 2005)
Place	China
City	Hainan
Period	19/12/05 → 21/12/05

Research Keywords

Alignment of trees
Constrained tree edit distance
Space efficient algorithms

Access Output

10.1007/11602613_39

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{97e3d1ff918a41cf921a5bea5db612f7,

title = "Space efficient algorithms for ordered tree comparison",

abstract = "In this paper we present techniques to significantly improve the space complexity of several ordered tree comparison algorithms with-out 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. {\textcopyright} Springer-Verlag Berlin Heidelberg 2005.",

keywords = "Alignment of trees, Constrained tree edit distance, Space efficient algorithms",

author = "Lusheng Wang and Kaizhong Zhang",

year = "2005",

doi = "10.1007/11602613\_39",

language = "English",

isbn = "9783540309352",

series = "Lecture Notes in Computer Science ",

publisher = "Springer ",

pages = "380--391",

editor = "Deng, \{Xiaotie \} and Du, \{Ding-Zhu \}",

booktitle = "Algorithms and Computation",

note = "16th International Symposium on Algorithms and Computation (ISAAC 2005) ; Conference date: 19-12-2005 Through 21-12-2005",

}

Wang, L & Zhang, K 2005, Space efficient algorithms for ordered tree comparison. in X Deng & D-Z Du (eds), Algorithms and Computation: 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings. Lecture Notes in Computer Science , vol. 3827, Springer , Berlin, Heidelberg, pp. 380-391, 16th International Symposium on Algorithms and Computation (ISAAC 2005), Hainan, China, 19/12/05. https://doi.org/10.1007/11602613_39

Space efficient algorithms for ordered tree comparison. / Wang, Lusheng; Zhang, Kaizhong.
Algorithms and Computation: 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings. ed. / Xiaotie Deng; Ding-Zhu Du. Berlin, Heidelberg: Springer , 2005. p. 380-391 (Lecture Notes in Computer Science ; Vol. 3827).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Space efficient algorithms for ordered tree comparison

AU - Wang, Lusheng

AU - Zhang, Kaizhong

PY - 2005

Y1 - 2005

N2 - In this paper we present techniques to significantly improve the space complexity of several ordered tree comparison algorithms with-out 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. © Springer-Verlag Berlin Heidelberg 2005.

AB - In this paper we present techniques to significantly improve the space complexity of several ordered tree comparison algorithms with-out 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. © Springer-Verlag Berlin Heidelberg 2005.

KW - Alignment of trees

KW - Constrained tree edit distance

KW - Space efficient algorithms

UR - https://www.scopus.com/pages/publications/33744961687

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-33744961687&origin=recordpage

U2 - 10.1007/11602613_39

DO - 10.1007/11602613_39

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783540309352

T3 - Lecture Notes in Computer Science

SP - 380

EP - 391

BT - Algorithms and Computation

A2 - Deng, Xiaotie

A2 - Du, Ding-Zhu

PB - Springer

CY - Berlin, Heidelberg

T2 - 16th International Symposium on Algorithms and Computation (ISAAC 2005)

Y2 - 19 December 2005 through 21 December 2005

ER -

Space efficient algorithms for ordered tree comparison

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this