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

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

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

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 programmingapproximation algorithmsparameterized algorithmstree edit distanceunordered trees

Mathematics Subject Classification ID

Trees (05C05) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (7)

Tai mapping hierarchy for rooted labeled trees through common subforest ⋮ TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE ⋮ Efficient exponential-time algorithms for edit distance between unordered trees ⋮ Trees with large numbers of subtrees ⋮ Unnamed Item ⋮ New and improved algorithms for unordered tree inclusion ⋮ On the complexity of finding a largest common subtree of bounded degree

This page was built for publication: Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees