Efficient lower and upper bounds of the diagonal-flip distance between triangulations

DOI10.1016/j.ipl.2006.07.001zbMath1185.68845OpenAlexW2148845695MaRDI QIDQ845849

Jean-Marcel Pallo, Jean-Luc Baril

Publication date: 29 January 2010

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.07.001

zbMATH Keywords

triangulationsapproximation algorithmsdiagonal-flip distance

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items

Restricted rotation distance between k-ary trees, Distributions of restricted rotation distances, The pruning-grafting lattice of binary trees, Lower bounds on the rotation distance of binary trees, Refined upper bounds for right-arm rotation distances, A metric for rooted trees with unlabeled vertices based on nested parentheses, The rotation distance of brooms, Flip distance between two triangulations of a point set is NP-complete, Edge Conflicts do not Determine Geodesics in the Associahedron, The Fermat star of binary trees, Rotation distance is fixed-parameter tractable, A Motzkin filter in the Tamari lattice, Motzkin subposets and Motzkin geodesics in Tamari lattices.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Right-arm rotation distance between binary trees
• Bounding restricted rotation distance
• 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
• Restricted rotation distance between binary trees.
• A direct algorithm for restricted rotation distance
• Enumerating, Ranking and Unranking Binary Trees
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• An efficient algorithm for estimating rotation distance between two binary trees
• Algorithms and Data Structures