A faster and unifying algorithm for comparing trees

Ming Yang Kao, Tak Wah Lam, Wing Kin Sung, Hing Fung Ting

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A widely-used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees. Previous work on this similarity measure only concerns with the comparison of labeled trees of two special kinds, namely, uniformly labeled trees (i.e., trees with all their nodes labeled by the same symbol) and evolutionary trees (i.e., leaf-labeled trees with distinct symbols for distinct leaves). This paper presents an algorithm for comparing trees that are labeled in an arbitrary manner. In addition to the generalization, our algorithm is faster than the previous algorithms in many cases.

Original languageEnglish (US)
Title of host publicationCombinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings
EditorsDavid Sankoff, Raffaele Giancarlo
PublisherSpringer Verlag
Pages129-142
Number of pages14
ISBN (Electronic)3540676333, 9783540676331
StatePublished - Jan 1 2000
Event11th Annual Symposium on Combinatorial Pattern Matching, CPM 2000 - Montreal, Canada
Duration: Jun 21 2000Jun 23 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1848
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other11th Annual Symposium on Combinatorial Pattern Matching, CPM 2000
CountryCanada
CityMontreal
Period6/21/006/23/00

Fingerprint

Labeled Trees
Leaves
Evolutionary Tree
Distinct
Similarity Measure
Arbitrary
Vertex of a graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Kao, M. Y., Lam, T. W., Sung, W. K., & Ting, H. F. (2000). A faster and unifying algorithm for comparing trees. In D. Sankoff, & R. Giancarlo (Eds.), Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings (pp. 129-142). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1848). Springer Verlag.
Kao, Ming Yang ; Lam, Tak Wah ; Sung, Wing Kin ; Ting, Hing Fung. / A faster and unifying algorithm for comparing trees. Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings. editor / David Sankoff ; Raffaele Giancarlo. Springer Verlag, 2000. pp. 129-142 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{9a3e945c40894bca92fe3101700b65e7,
title = "A faster and unifying algorithm for comparing trees",
abstract = "A widely-used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees. Previous work on this similarity measure only concerns with the comparison of labeled trees of two special kinds, namely, uniformly labeled trees (i.e., trees with all their nodes labeled by the same symbol) and evolutionary trees (i.e., leaf-labeled trees with distinct symbols for distinct leaves). This paper presents an algorithm for comparing trees that are labeled in an arbitrary manner. In addition to the generalization, our algorithm is faster than the previous algorithms in many cases.",
author = "Kao, {Ming Yang} and Lam, {Tak Wah} and Sung, {Wing Kin} and Ting, {Hing Fung}",
year = "2000",
month = "1",
day = "1",
language = "English (US)",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "129--142",
editor = "David Sankoff and Raffaele Giancarlo",
booktitle = "Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings",
address = "Germany",

}

Kao, MY, Lam, TW, Sung, WK & Ting, HF 2000, A faster and unifying algorithm for comparing trees. in D Sankoff & R Giancarlo (eds), Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1848, Springer Verlag, pp. 129-142, 11th Annual Symposium on Combinatorial Pattern Matching, CPM 2000, Montreal, Canada, 6/21/00.

A faster and unifying algorithm for comparing trees. / Kao, Ming Yang; Lam, Tak Wah; Sung, Wing Kin; Ting, Hing Fung.

Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings. ed. / David Sankoff; Raffaele Giancarlo. Springer Verlag, 2000. p. 129-142 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1848).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - A faster and unifying algorithm for comparing trees

AU - Kao, Ming Yang

AU - Lam, Tak Wah

AU - Sung, Wing Kin

AU - Ting, Hing Fung

PY - 2000/1/1

Y1 - 2000/1/1

N2 - A widely-used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees. Previous work on this similarity measure only concerns with the comparison of labeled trees of two special kinds, namely, uniformly labeled trees (i.e., trees with all their nodes labeled by the same symbol) and evolutionary trees (i.e., leaf-labeled trees with distinct symbols for distinct leaves). This paper presents an algorithm for comparing trees that are labeled in an arbitrary manner. In addition to the generalization, our algorithm is faster than the previous algorithms in many cases.

AB - A widely-used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees. Previous work on this similarity measure only concerns with the comparison of labeled trees of two special kinds, namely, uniformly labeled trees (i.e., trees with all their nodes labeled by the same symbol) and evolutionary trees (i.e., leaf-labeled trees with distinct symbols for distinct leaves). This paper presents an algorithm for comparing trees that are labeled in an arbitrary manner. In addition to the generalization, our algorithm is faster than the previous algorithms in many cases.

UR - http://www.scopus.com/inward/record.url?scp=84937459112&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84937459112&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84937459112

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 129

EP - 142

BT - Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings

A2 - Sankoff, David

A2 - Giancarlo, Raffaele

PB - Springer Verlag

ER -

Kao MY, Lam TW, Sung WK, Ting HF. A faster and unifying algorithm for comparing trees. In Sankoff D, Giancarlo R, editors, Combinatorial Pattern Matching - 11th Annual Symposium, CPM 2000, Proceedings. Springer Verlag. 2000. p. 129-142. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).