A fast algorithm for optimal alignment between similar ordered trees

Jesper Andreas Jansson, Andrzej Lingas

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

15 Citations (Scopus)

Abstract

We present a fast algorithm for optimal alignment between two similar ordered trees with node labels. Let S and T be two such trees with |S| and |T| nodes, respectively. An optimal alignment between S and T which uses at most d blank symbols can be constructed in O(n log n. (maxdeg)4. d2) time, where n = maxf{|S|,|T|} and maxdeg is the maximum degree of a node in S or T. In particular, if the input trees are of bounded degree, the running time is O(n log n. d2).
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 12th Annual Symposium, CPM 2001, Proceedings
PublisherSpringer Verlag
Pages232-240
Number of pages9
ISBN (Print)3540422714, 9783540422716
Publication statusPublished - 1 Jan 2001
Externally publishedYes
Event12th Annual Symposium on Combinatorial Pattern Matching, CPM 2001 - Jerusalem, Israel
Duration: 1 Jul 20014 Jul 2001

Publication series

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

Conference

Conference12th Annual Symposium on Combinatorial Pattern Matching, CPM 2001
Country/TerritoryIsrael
CityJerusalem
Period1/07/014/07/01

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this