Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees
From MaRDI portal
Publication:3011871
DOI10.1007/978-3-642-21458-5_34zbMath1339.68105WikidataQ58061259 ScholiaQ58061259MaRDI QIDQ3011871
Yoshiyuki Yamamoto, Kouichi Hirata, Tetsuji Kuboyama
Publication date: 29 June 2011
Published in: Combinatorial Pattern Matching (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-21458-5_34
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68P05: Data structures
Related Items
On the complexity of finding a largest common subtree of bounded degree, Tai mapping hierarchy for rooted labeled trees through common subforest, Efficient exponential-time algorithms for edit distance between unordered trees, TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE
Cites Work
- A survey on tree edit distance and related problems
- Alignment of trees -- an alternative to tree edit
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Optimization, approximation, and complexity classes
- On the editing distance between unordered labeled trees
- Some MAX SNP-hard results concerning unordered labeled trees
- An optimal decomposition algorithm for tree edit distance
- Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
- The Tree-to-Tree Correction Problem
- ON THE EDITING DISTANCE BETWEEN UNDIRECTED ACYCLIC GRAPHS
- Exact and approximate algorithms for unordered tree matching
