A metric for rooted trees with unlabeled vertices based on nested parentheses
From MaRDI portal
Publication:410711
DOI10.1016/j.tcs.2010.08.003zbMath1238.68112MaRDI QIDQ410711
Chan-Shuo Wu, Guan-Shieng Huang
Publication date: 3 April 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.003
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Two shortest path metrics on well-formed parentheses strings
- A survey on tree edit distance and related problems
- Alignment of trees -- an alternative to tree edit
- Rotation sequences and edge-colouring of binary tree pairs
- A relation between edit distance for ordered trees and edit distance for Euler strings
- Efficient lower and upper bounds of the diagonal-flip distance between triangulations
- On the rotation distance between binary trees
- Refined upper bounds for right-arm rotation distances
- A distance metric on binary trees using lattice-theoretic measures
- Rotation distance is fixed-parameter tractable
- Bounding restricted rotation distance
- Embedding planar graphs in four pages
- A note on some tree similarity measures
- Some simplified NP-complete graph problems
- An efficient upper bound of the rotation distance of binary trees
- On the upper bound on the rotation distance of binary trees
- Restricted rotation distance between binary trees.
- The longest common subsequence problem for sequences with nested arc annotations.
- A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations
- Property testing of regular tree languages
- Rotation Distance, Triangulations, and Hyperbolic Geometry
- The Tree-to-Tree Correction Problem
- On Rotations and the Generation of Binary Trees
- Approximation algorithms for NP-complete problems on planar graphs
- Algorithms and Data Structures
- Combinatorial Pattern Matching
