Rotation distance is fixed-parameter tractable

DOI10.1016/J.IPL.2009.04.023MaRDI QIDQ989526zbMATH OpenOpenAlexFDO

Authors Sean Cleary, Katherine St. John

Publication date 20 August 2010

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

Full work available at URL https://arxiv.org/abs/0903.0197

zbMATH Keywords

analysis of algorithmscomputational complexityfixed parameter tractabilityrotation distance

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Abstract: Rotation distance between trees measures the number of simple operations it takes to transform one tree into another. There are no known polynomial-time algorithms for computing rotation distance. In the case of ordered rooted trees, we show that the rotation distance between two ordered trees is fixed-parameter tractable, in the parameter, k, the rotation distance. The proof relies on the kernalization of the initial trees to trees with size bounded by 7k.

Recommendations

• An improved kernel size for rotation distance in binary trees
• A linear-time approximation algorithm for rotation distance
• scientific article; zbMATH DE number 1161281
• On the rotation distance of graphs
• On the upper bound on the rotation distance of binary trees

Cites work

• A note on some tree similarity measures
• An efficient upper bound of the rotation distance of binary trees
• Bounding restricted rotation distance
• BOUNDING RIGHT-ARM ROTATION DISTANCES
• Computing the minimum number of hybridization events for a consistent evolutionary history
• Efficient lower and upper bounds of the diagonal-flip distance between triangulations
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1407500 (Why is no real title available?)
• scientific article; zbMATH DE number 1439421 (Why is no real title available?)
• On the computational complexity of the rooted subtree prune and regraft distance
• Restricted rotation distance between binary trees.
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Subtree transfer operations and their induced metrics on evolutionary trees
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization

Cited in

(24)

• Fixed-parameter tractability for the tree assembly problem
• Neighborhoods of trees in circular orderings
• Computing the flip distance between triangulations
• Flip distance between triangulations of a planar point set is APX-hard
• A linear-time approximation algorithm for rotation distance
• A metric for rooted trees with unlabeled vertices based on nested parentheses
• Edge Conflicts do not Determine Geodesics in the Associahedron
• Kernelization of Whitney switches
• Distributions of restricted rotation distances
• Kernelization of Whitney Switches
• Restricted rotation distance between k-ary trees
• On flips in planar matchings
• Flip distances between graph orientations
• A survey of parameterized algorithms and the complexity of edge modification
• An improved kernel for the flip distance problem on simple convex polygons
• Rotation distance for rank bounded trees
• The rotation distance of brooms
• Shallow-rotation distance via forest representations
• Shortest paths on polymatroids and hypergraphic polytopes
• An \(\mathcal{O}(3.82^k)\) time \(\mathsf{FPT}\) algorithm for convex flip distance
• Hardness of finding combinatorial shortest paths on graph associahedra
• An improved kernel size for rotation distance in binary trees
• On the rotation distance between binary trees
• Flip distance between two triangulations of a point set is NP-complete

This page was built for publication: Rotation distance is fixed-parameter tractable

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