Constrained tree inclusion

DOI10.1016/j.jda.2004.08.017zbMath1129.68096OpenAlexW2072851563MaRDI QIDQ2569419

Gabriel Valiente

Publication date: 27 October 2005

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2004.08.017

zbMATH Keywords

combinatorial algorithmstree pattern matchingtree inclusionsubtree isomorphismsubtree homeomorphismnoncrossing bipartite matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Generalized LCS ⋮ Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism ⋮ Faster Bit-Parallel Algorithms for Unordered Pseudo-tree Matching and Tree Homeomorphism ⋮ A top down algorithm for constrained tree inclusion ⋮ Algorithms for finding a most similar subforest ⋮ Unnamed Item ⋮ An algebraic view of the relation between largest common subtrees and smallest common supertrees ⋮ New and improved algorithms for unordered tree inclusion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some comments on the subtree isomorphism problem for ordered trees
• On the subtree isomorphism problem for ordered trees
• A note on the subtree isomorphism for ordered trees and related problems
• Further comments on the subtree isomorphism for ordered trees
• Optimal canonization of all substrings of a string
• Strings, trees, and patterns
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
• Efficient labelling algorithms for the maximum noncrossing matching problem
• Constrained Tree Inclusion
• O(n2.5) time algorithms for the subgraph homeomorphism problem on trees
• Efficient randomized pattern-matching algorithms
• An Analysis of a Good Algorithm for the Subtree Problem, Corrected
• An Analysis of a Good Algorithm for the Subtree Problem
• Fast Pattern Matching in Strings
• Subtree Isomorphism in O(n5/2)
• More Efficient Algorithm for Ordered Tree Inclusion
• Ordered and Unordered Tree Inclusion
• ON THE EDITING DISTANCE BETWEEN UNDIRECTED ACYCLIC GRAPHS
• Faster Subtree Isomorphism
• FINDING SMALLEST SUPERTREES UNDER MINOR CONTAINMENT
• Combinatorial Pattern Matching
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• On the tree inclusion problem

This page was built for publication: Constrained tree inclusion