A note on some tree similarity measures

DOI10.1016/0020-0190(82)90083-7zbMath0489.68058OpenAlexW2095120546MaRDI QIDQ1166933

Karel II Culik, Derick Wood

Publication date: 1982

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(82)90083-7

zbMATH Keywords

upper boundsdistance measuretree metricslabelled treesdendrogramsfree trees

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (40)

Computing the nearest neighbor interchange metric for unlabeled binary trees is NP-complete ⋮ Restricted rotation distance between k-ary trees ⋮ A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations ⋮ Distributions of restricted rotation distances ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ BOUNDING RIGHT-ARM ROTATION DISTANCES ⋮ Average-case analysis via incompressibility ⋮ Neighborhoods of Phylogenetic Trees: Exact and Asymptotic Counts ⋮ Efficient lower and upper bounds of the diagonal-flip distance between triangulations ⋮ A direct algorithm for restricted rotation distance ⋮ An efficient algorithm for estimating rotation distance between two binary trees ⋮ Unnamed Item ⋮ Lower bounds on the rotation distance of binary trees ⋮ Refined upper bounds for right-arm rotation distances ⋮ Flip distance between triangulations of a simple polygon is NP-complete ⋮ A metric for rooted trees with unlabeled vertices based on nested parentheses ⋮ An improved kernel for the flip distance problem on simple convex polygons ⋮ Rotation distance for rank bounded trees ⋮ The rotation distance of brooms ⋮ Flip distance between two triangulations of a point set is NP-complete ⋮ Flip distance between triangulations of a planar point set is APX-hard ⋮ Some notes on the nearest neighbour interchange distance ⋮ Cubic graphs, their Ehrhart quasi-polynomials, and a scissors congruence phenomenon ⋮ Edge Conflicts do not Determine Geodesics in the Associahedron ⋮ Flipping in spirals ⋮ On the deque conjecture for the splay algorithm ⋮ Discriminative measures for comparison of phylogenetic trees ⋮ The cost of offline binary search tree algorithms and the complexity of the request sequence ⋮ Computing spin networks ⋮ Rotation sequences and edge-colouring of binary tree pairs ⋮ Rotation distance is fixed-parameter tractable ⋮ An improved kernel size for rotation distance in binary trees ⋮ On the upper bound on the rotation distance of binary trees ⋮ Rotation Distance, Triangulations, and Hyperbolic Geometry ⋮ APPROXIMATING THE NEAREST NEIGHBOR INTERCHARGE DISTANCE FOR NON-UNIFORM-DEGREE EVOLUTIONARY TREES ⋮ A computationally efficient approximation to the nearest neighbor interchange metric ⋮ Restricted rotation distance between binary trees. ⋮ An efficient upper bound of the rotation distance of binary trees ⋮ Sequential access in splay trees takes linear time

Cites Work

• Unnamed Item
• Axioms and hulls
• The String-to-String Correction Problem
• Syntax-directed least-errors analysis for context-free languages
• Matching Sequences under Deletion/Insertion Constraints
• A Minimum Distance Error-Correcting Parser for Context-Free Languages

This page was built for publication: A note on some tree similarity measures