Lower bounds on the rotation distance of binary trees

DOI10.1016/j.ipl.2010.07.025zbMath1379.05026OpenAlexW1990400455MaRDI QIDQ1675757

Linda Pagli, Antonio Mesa Enriquez, Fabrizio Luccio

Publication date: 3 November 2017

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

Full work available at URL: http://eprints.adm.unipi.it/2245/1/TR%2D10%2D01.pdf.gz

zbMATH Keywords

binary treelower bounddesign of algorithmsrotation distance

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12)

Related Items (3)

Flip distance between two triangulations of a point set is NP-complete ⋮ Flip distances between graph orientations ⋮ Neighborhoods of trees in circular orderings

Cites Work

• An improved kernel size for rotation distance in binary trees
• Efficient lower and upper bounds of the diagonal-flip distance between triangulations
• On the rotation distance between binary trees
• A note on some tree similarity measures
• An efficient upper bound of the rotation distance of binary trees
• On the upper bound on the rotation distance of binary trees
• A Linear-Time Approximation Algorithm for Rotation Distance
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• An efficient algorithm for estimating rotation distance between two binary trees
• Unnamed Item

This page was built for publication: Lower bounds on the rotation distance of binary trees