An improved kernel size for rotation distance in binary trees

DOI10.1016/J.IPL.2010.04.022zbMATH Open1233.68147OpenAlexW2026496675MaRDI QIDQ763531FDOQ763531

Joan M. Lucas

Publication date: 12 March 2012

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.04.022

Recommendations

• Rotation distance is fixed-parameter tractable
• scientific article; zbMATH DE number 1161281
• On the upper bound on the rotation distance of binary trees
• A linear-time approximation algorithm for rotation distance
• \(k\)-restricted rotation distance between binary trees

zbMATH Keywords

fixed-parameter tractabilitycombinatorial problemsrotation distance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Cites Work

• Parametrized complexity theory.
• Title not available (Why is that?)
• Self-adjusting binary search trees
• Title not available (Why is that?)
• Generating binary trees by transpositions
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• Title not available (Why is that?)
• Generating binary trees using rotations
• The rotation graph of binary trees is Hamiltonian
• On Rotations and the Generation of Binary Trees
• Vertex cover: Further observations and further improvements
• A note on some tree similarity measures
• On the upper bound on the rotation distance of binary trees
• Rotation distance is fixed-parameter tractable
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization
• Graph of triangulations of a convex polygon and tree of triangulations
• Short notes: Some Properties of the Rotation Lattice of Binary Trees
• Title not available (Why is that?)
• General Balanced Trees
• An efficient algorithm for estimating rotation distance between two binary trees
• Relaxed balance using standard rotations

Cited In (12)

• Kernelization of Whitney Switches
• Kernelization of Whitney Switches
• Lower bounds on the rotation distance of binary trees
• A survey of parameterized algorithms and the complexity of edge modification
• Title not available (Why is that?)
• The rotation distance of brooms
• Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance
• An improved kernel for the flip distance problem on simple convex polygons
• The edge rotation graph
• An improved FPT algorithm for the flip distance problem
• Title not available (Why is that?)
• Computing the flip distance between triangulations

This page was built for publication: An improved kernel size for rotation distance in binary trees

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