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 (13)

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

This page was built for publication: Efficient lower and upper bounds of the diagonal-flip distance between triangulations