Rotation distance is fixed-parameter tractable

DOI10.1016/j.ipl.2009.04.023zbMath1205.68531arXiv0903.0197OpenAlexW2013007461MaRDI QIDQ989526

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

computational complexityanalysis of algorithmsfixed parameter tractabilityrotation distance

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Related Items

Restricted rotation distance between k-ary trees ⋮ Distributions of restricted rotation distances ⋮ Computing the flip distance between triangulations ⋮ A metric for rooted trees with unlabeled vertices based on nested parentheses ⋮ 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 ⋮ Flip distance between two triangulations of a point set is NP-complete ⋮ Flip distance between triangulations of a planar point set is APX-hard ⋮ Edge Conflicts do not Determine Geodesics in the Associahedron ⋮ Reconfiguration on sparse graphs ⋮ On flips in planar matchings ⋮ Flip distances between graph orientations ⋮ An improved kernel size for rotation distance in binary trees ⋮ Kernelization of Whitney Switches ⋮ Kernelization of Whitney Switches ⋮ Neighborhoods of trees in circular orderings

Cites Work

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