Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees

DOI10.1016/j.tcs.2012.11.017zbMath1258.68102MaRDI QIDQ1935809

Magnús M. Halldórsson, Tatsuya Akutsu, Daiji Fukagawa, Atsuhiro Takasu, Keisuke Tanaka

Publication date: 19 February 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.11.017

zbMATH Keywords

dynamic programming; approximation algorithms; parameterized algorithms; tree edit distance; unordered trees

Mathematics Subject Classification ID

05C05: Trees

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms