An algebraic view of the relation between largest common subtrees and smallest common supertrees

DOI10.1016/j.tcs.2006.05.031zbMath1111.68091arXivcs/0604108OpenAlexW2081574366MaRDI QIDQ2508961

Gabriel Valiente, Francesc Rosselló

Publication date: 20 October 2006

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

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

zbMATH Keywords

tree pattern matchingtopological embeddingsubtree isomorphismsubtree homeomorphismlargest common subtreeminor containmentsmallest common supertree

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Forest alignment with affine gaps and anchors, applied in RNA structure comparison ⋮ On the parameterized complexity of the multi-MCT and multi-MCST problems ⋮ On the ancestral compatibility of two phylogenetic trees with nested taxa ⋮ Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems ⋮ Forest Alignment with Affine Gaps and Anchors

Cites Work

• Unnamed Item
• Unnamed Item
• Alignment of trees -- an alternative to tree edit
• The longest common subsequence problem for arc-annotated sequences
• Approximate labelled subtree homeomorphism
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Kaikoura tree theorems: Computing the maximum agreement subtree
• Finding largest subtrees and smallest supertrees
• RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm.
• Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees
• Constrained tree inclusion
• An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Constrained Tree Inclusion
• O(n2.5) time algorithms for the subgraph homeomorphism problem on trees
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• A graph distance metric combining maximum common subgraph and minimum common supergraph
• Ordered and Unordered Tree Inclusion
• Faster Subtree Isomorphism
• FINDING SMALLEST SUPERTREES UNDER MINOR CONTAINMENT
• Exact and approximate algorithms for unordered tree matching
• Fast algorithms for the unit cost editing distance between trees