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

DOI10.1016/J.IPL.2006.07.001MaRDI QIDQ845849zbMATH OpenOpenAlexFDO

Authors Jean-Luc Baril, Jean Pallo

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)

Recommendations

• An efficient upper bound of the rotation distance of binary trees
• Publication:4942049
• On the rotation distance between binary trees
• scientific article; zbMATH DE number 1222822
• Computing the flip distance between triangulations

Cites work

• scientific article; zbMATH DE number 1161281 (Why is no real title available?)
• scientific article; zbMATH DE number 1418487 (Why is no real title available?)
• scientific article; zbMATH DE number 1439421 (Why is no real title available?)
• A direct algorithm for restricted rotation distance
• A note on some tree similarity measures
• Algorithms and Data Structures
• An efficient algorithm for estimating rotation distance between two binary trees
• An efficient upper bound of the rotation distance of binary trees
• Bounding restricted rotation distance
• Enumerating, Ranking and Unranking Binary Trees
• On the upper bound on the rotation distance of binary trees
• Restricted rotation distance between binary trees.
• Right-arm rotation distance between binary trees
• Rotation Distance, Triangulations, and Hyperbolic Geometry

Cited in

(17)

• The pruning-grafting lattice of binary trees
• Edge Conflicts do not Determine Geodesics in the Associahedron
• The Fermat star of binary trees
• scientific article; zbMATH DE number 7204399 (Why is no real title available?)
• Motzkin subposets and Motzkin geodesics in Tamari lattices.
• A Motzkin filter in the Tamari lattice
• The rotation distance of brooms
• A metric for rooted trees with unlabeled vertices based on nested parentheses
• An efficient upper bound of the rotation distance of binary trees
• Rotation distance is fixed-parameter tractable
• scientific article; zbMATH DE number 1555932 (Why is no real title available?)
• Refined upper bounds for right-arm rotation distances
• Flip distance between two triangulations of a point set is NP-complete
• Expected maximum vertex valence in pairs of polygonal triangulations
• Distributions of restricted rotation distances
• Lower bounds on the rotation distance of binary trees
• Restricted rotation distance between k-ary trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845849)