34 citations · 34 across the 2 of their papers we have counts for
2 papers
cs.DS2007★ 34 cited
Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture
Seth Pettie
We introduce a new technique to bound the asymptotic performance of splay trees. The basic idea is to transcribe, in an indirect fashion, the rotations performed by the splay tree…
cs.DM2007
Sources of Superlinearity in Davenport-Schinzel Sequences
Seth Pettie
A generalized Davenport-Schinzel sequence is one over a finite alphabet that contains no subsequences isomorphic to a fixed forbidden subsequence. One of the fundamental problems i…