Rotation distance is fixed-parameter tractable
From MaRDI portal
Publication:989526
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
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