An improved kernel size for rotation distance in binary trees
From MaRDI portal
Publication:763531
DOI10.1016/j.ipl.2010.04.022zbMath1233.68147MaRDI QIDQ763531
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
Related Items
Unnamed Item, Kernelization of Whitney Switches, Kernelization of Whitney Switches, A survey of parameterized algorithms and the complexity of edge modification, An improved kernel for the flip distance problem on simple convex polygons, The rotation distance of brooms, The edge rotation graph, Lower bounds on the rotation distance of binary trees, An improved FPT algorithm for the flip distance problem, 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