Algorithms for finding a most similar subforest

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

3 Citations (Scopus)

Abstract

Given an ordered labeled forest F ("the target forest") and an ordered labeled forest G ("the pattern forest"), the most similar subforest problem is to find a subforest F′ of F such that the distance between F′ and G is minimum over all possible F'. This problem generalizes several well-studied problems which have important applications in locating patterns in hierarchical structures such as RNA molecules' secondary structures and XML documents. In this paper, we present efficient algorithms for the most similar subforest problem with forest edit distance for three types of subforests: simple substructures, sibling substructures, and closed subforests.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 17th Annual Symposium, CPM 2006, Proceedings
PublisherSpringer Verlag
Pages377-388
Number of pages12
ISBN (Print)3540354557, 9783540354550
DOIs
Publication statusPublished - 1 Jan 2006
Externally publishedYes
Event17th Annual Symposium on Combinatorial Pattern Matching, CPM 2006 - Barcelona, Spain
Duration: 5 Jul 20067 Jul 2006

Publication series

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

Conference

Conference17th Annual Symposium on Combinatorial Pattern Matching, CPM 2006
CountrySpain
CityBarcelona
Period5/07/067/07/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this