Some MAX SNP-hard results concerning unordered labeled trees
From MaRDI portal
Publication:1318750
DOI10.1016/0020-0190(94)90062-0zbMath0795.68073OpenAlexW2011975945MaRDI QIDQ1318750
Publication date: 5 April 1994
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(94)90062-0
computational complexityedit distancepolynomial time approximation schemecomparison between unordered labeled trees
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
A calculation method of plant similarity giving consideration to different plant features ⋮ A constrained edit distance between unordered labeled trees ⋮ Tai mapping hierarchy for rooted labeled trees through common subforest ⋮ TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE ⋮ Fast similarity search for graphs by edit distance ⋮ Exact algorithms for computing the tree edit distance between unordered trees ⋮ Multi-label classification and extracting predicted class hierarchies ⋮ Kernelization and parameterized algorithms for covering a tree by a set of stars or paths ⋮ Anti Tai mapping for unordered labeled trees ⋮ Efficient exponential-time algorithms for edit distance between unordered trees ⋮ Tree edit distance and maximum agreement subtree ⋮ Alignment of trees -- an alternative to tree edit ⋮ Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees ⋮ Improved approximation of the largest common subtree of two unordered trees of bounded height ⋮ A survey on tree edit distance and related problems ⋮ Data mining in an engineering design environment: OR applications from graph matching ⋮ Unnamed Item ⋮ Component reuse based agile reconfiguration for Enterprise Resource Planning (ERP) systems in manufacturing enterprises ⋮ A constrained edit distance algorithm between semi-ordered trees ⋮ FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees ⋮ New and improved algorithms for unordered tree inclusion ⋮ Alignment distance of regular tree languages ⋮ Alignment distance of regular tree languages ⋮ A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression. ⋮ FAST ALGORITHMS FOR COMPARISON OF SIMILAR UNORDERED TREES ⋮ On the complexity of finding a largest common subtree of bounded degree ⋮ Covering tree with stars
Cites Work
- Unnamed Item
- Unnamed Item
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Optimization, approximation, and complexity classes
- On the editing distance between unordered labeled trees
- Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
- Threshold decomposition of gray-scale morphology into binary morphology
- Ordered and Unordered Tree Inclusion
- On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
