7 votes

What are the must-read search trees paper?

Sleator-Tarjan '85 and Demaine et al '09 definitely belong on any such list. There is a lot of other recent work related to splay trees and dynamic optimality, for instance: Applications of forbidden ...
David Eppstein's user avatar
7 votes

Algorithms for tree rotation

It's fixed-parameter tractable in the natural parameter, the distance. So if two trees have distance $k$ you can find the distance in time polynomial + $f(k)$ for some function $f$. The proof is a ...
David Eppstein's user avatar
5 votes

Treewidth of two complete binary trees joined at their leaves

Indeed, this graph has treewidth 2. It's a well-known result in phylogenetics where the leaves are labelled. See Bryant, David, and Jens Lagergren. "Compatibility of unrooted phylogenetic trees is FPT....
steven kelk's user avatar
3 votes

Inexact labelled binary tree matching

I think that the problem is not hard, because if I understood the problem statement correctly, it can be solved in $O(|V|^2)$ time as follows: We have two $0$-$1$-labeled rooted perfect full binary ...
Topi Talvitie's user avatar
1 vote

Find an approximate argmax using only approximate max queries

Extended comment of an idea or two toward a lower bound. Let $B = \Theta(\log n)$, say (though the best choice may be different), and let $\{v_1,\dots,v_n\} = \{\frac{1}{n}B, \dots, \frac{n-1}{n}B, B\}...
usul's user avatar
  • 7,555
1 vote

Amortized analysis of red-black trees

You may need to look at this report: https://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf Each individual operation takes $O(\log n)$ but when you apply amortized ...
Hung Le's user avatar
  • 305

Only top scored, non community-wiki answers of a minimum length are eligible