An improved kernel size for rotation distance in binary trees

DOI10.1016/J.IPL.2010.04.022MaRDI QIDQ763531zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

fixed-parameter tractabilitycombinatorial problemsrotation distance

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(13)

• An improved FPT algorithm for the flip distance problem
• scientific article; zbMATH DE number 6739965 (Why is no real title available?)
• Computing the flip distance between triangulations
• scientific article; zbMATH DE number 7204399 (Why is no real title available?)
• The rotation distance of brooms
• The edge rotation graph
• Kernelization of Whitney Switches
• Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance
• Rotation distance is fixed-parameter tractable
• Kernelization of Whitney switches
• A survey of parameterized algorithms and the complexity of edge modification
• Lower bounds on the rotation distance of binary trees
• An improved kernel for the flip distance problem on simple convex polygons

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)