Efficient exponential time algorithms for edit distance between unordered trees

DOI10.1007/978-3-642-31265-6_29MaRDI QIDQ2904510zbMATH OpenOpenAlexFDO

Authors Tatsuya Akutsu, Daiji Fukagawa, Atsuhiro Takasu

Publication date 14 August 2012

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31265-6_29

zbMATH Keywords

dynamic programmingmaximum weight bipartite matchingtree edit distanceunordered trees

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Efficient exponential-time algorithms for edit distance between unordered trees
• Exact algorithms for computing the tree edit distance between unordered trees
• A constrained edit distance between unordered labeled trees
• On the editing distance between unordered labeled trees
• Alignment of trees -- an alternative to tree edit

Cited in

(5)

• Improved methods for computing distances between unordered trees using integer programming
• On the complexity of finding a largest common subtree of bounded degree
• Efficient exponential-time algorithms for edit distance between unordered trees
• Inexact tree pattern matching with 1-degree edit distance using finite automata
• Exact algorithms for computing the tree edit distance between unordered trees

This page was built for publication: Efficient exponential time algorithms for edit distance between unordered trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904510)