Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On the maximum common embedded subtree problem for ordered trees

Autor
Valiente, G.
Tipus d'activitat
Document cientificotècnic
Data
2003-03
Codi
LSI-03-8-R
Repositori
http://hdl.handle.net/2117/97381 Obrir en finestra nova
Resum
The maximum common embedded subtree problem, which generalizes the subtree homeomorphism problem, is reduced for ordered trees to a variant of the longest common subsequence problem, called the longest common balanced sequence problem. While the maximum common embedded subtree problem is known to be APX-hard for unordered trees, an exact solution for ordered trees can be found in polynomial time. A dynamic programming algorithm is presented that solves the longest common balanced sequence proble...
Citació
Valiente, G. "On the maximum common embedded subtree problem for ordered trees". 2003.
Paraules clau
Combinatorial problems, Graph algorithms, Longest common balanced sequence, Maximum common embedded subtree, Pattern matching subtree isomorphism, String algorithms, Subtree homeomorphism, Trees
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

Arxius