An algebraic view of the relation between largest common subtrees and smallest common supertrees
From MaRDI portal
Publication:2508961
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
tree pattern matchingtopological embeddingsubtree isomorphismsubtree homeomorphismlargest common subtreeminor containmentsmallest common supertree
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