New and improved algorithms for unordered tree inclusion

DOI10.1016/j.tcs.2021.06.013OpenAlexW3173543202MaRDI QIDQ2049980

Tatsuya Akutsu, Takeyuki Tamura, Atsuhiro Takasu, Ruiming Li, Jesper Jansson

Publication date: 27 August 2021

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

Full work available at URL: https://arxiv.org/abs/1712.05517

zbMATH Keywords

dynamic programmingparameterized algorithmsunordered treestree inclusion

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

• KEGG
• TED
• RTED

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey on tree edit distance and related problems
• Exact algorithms for computing the tree edit distance between unordered trees
• On the editing distance between unordered labeled trees
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Some MAX SNP-hard results concerning unordered labeled trees
• Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees
• Efficient exponential-time algorithms for edit distance between unordered trees
• Constrained tree inclusion
• The tree inclusion problem
• The Tree-to-Tree Correction Problem
• Color-coding
• Subtree Isomorphism Revisited
• Ordered and Unordered Tree Inclusion
• Consequences of Faster Alignment of Sequences
• 1+ ε approximation of tree edit distance in quadratic time
• Exact and approximate algorithms for unordered tree matching
• Depth-First Search and Linear Graph Algorithms
• Algorithms and Computation

This page was built for publication: New and improved algorithms for unordered tree inclusion