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

DOI10.1016/J.IPL.2006.07.001zbMATH Open1185.68845OpenAlexW2148845695MaRDI QIDQ845849FDOQ845849

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

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

zbMATH Keywords

triangulationsapproximation algorithmsdiagonal-flip distance

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cites Work

• Restricted rotation distance between binary trees.
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Title not available (Why is that?)
• Enumerating, Ranking and Unranking Binary Trees
• An efficient upper bound of the rotation distance of binary trees
• Bounding restricted rotation distance
• A note on some tree similarity measures
• On the upper bound on the rotation distance of binary trees
• Algorithms and Data Structures
• Right-arm rotation distance between binary trees
• Title not available (Why is that?)
• An efficient algorithm for estimating rotation distance between two binary trees
• A direct algorithm for restricted rotation distance
• Title not available (Why is that?)

Cited In (17)

• An efficient upper bound of the rotation distance of binary trees
• Flip distance between two triangulations of a point set is NP-complete
• A metric for rooted trees with unlabeled vertices based on nested parentheses
• Refined upper bounds for right-arm rotation distances
• The Fermat star of binary trees
• A Motzkin filter in the Tamari lattice
• Rotation distance is fixed-parameter tractable
• Title not available (Why is that?)
• Edge Conflicts do not Determine Geodesics in the Associahedron
• The pruning-grafting lattice of binary trees
• Lower bounds on the rotation distance of binary trees
• Title not available (Why is that?)
• The rotation distance of brooms
• Distributions of restricted rotation distances
• Motzkin subposets and Motzkin geodesics in Tamari lattices.
• Expected maximum vertex valence in pairs of polygonal triangulations
• 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)