An improved kernel size for rotation distance in binary trees

DOI10.1016/j.ipl.2010.04.022zbMath1233.68147MaRDI QIDQ763531

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

combinatorial problems; fixed-parameter tractability; rotation distance

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

Related Items

The edge rotation graph, Lower bounds on the rotation distance of binary trees, Computing the flip distance between triangulations

Cites Work

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