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


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
EditorsRaffaele Giancarlo, David Sankoff
PublisherSpringer Verlag
Number of pages14
ISBN (Electronic)3540676333, 9783540676331
StatePublished - 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)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other11th Annual Symposium on Combinatorial Pattern Matching, CPM 2000

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A faster and unifying algorithm for comparing trees'. Together they form a unique fingerprint.

Cite this