Rotation distance is fixed-parameter tractable

DOI10.1016/J.IPL.2009.04.023zbMATH Open1205.68531arXiv0903.0197OpenAlexW2013007461MaRDI QIDQ989526FDOQ989526

Authors: Sean Cleary, Katherine St. John 

Publication date: 20 August 2010

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

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.

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

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

zbMATH Keywords

computational complexityanalysis of algorithmsfixed parameter tractabilityrotation distance

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Cites Work

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

Cited In (21)

• Flip distance between two triangulations of a point set is NP-complete
• A metric for rooted trees with unlabeled vertices based on nested parentheses
• Kernelization of Whitney Switches
• Fixed-parameter tractability for the tree assembly problem
• On the rotation distance between binary trees
• Edge Conflicts do not Determine Geodesics in the Associahedron
• On flips in planar matchings
• Neighborhoods of trees in circular orderings
• A linear-time approximation algorithm for rotation distance
• A survey of parameterized algorithms and the complexity of edge modification
• The rotation distance of brooms
• An improved kernel for the flip distance problem on simple convex polygons
• Distributions of restricted rotation distances
• Kernelization of Whitney switches
• Restricted rotation distance between k-ary trees
• Rotation distance for rank bounded trees
• An improved kernel size for rotation distance in binary trees
• Flip distance between triangulations of a planar point set is APX-hard
• Flip distances between graph orientations
• Computing the flip distance between triangulations
• Reconfiguration on sparse graphs

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)