7
votes
Accepted
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 ...
- 50.8k
7
votes
Accepted
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 ...
- 50.8k
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....
- 71
3
votes
Accepted
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 ...
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\}...
- 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 ...
- 305
Only top scored, non community-wiki answers of a minimum length are eligible