A new path from Splay to dynamic optimality

DOI10.1137/1.9781611975482.80MaRDI QIDQ5236264zbMATH OpenOpenAlexFDO

Authors Caleb C. Levy, Robert E. Tarjan

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611975482.80

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Searching and sorting (68P10)

Recommendations

• In pursuit of the dynamic optimality conjecture
• A study on splay trees
• scientific article; zbMATH DE number 5237331
• Sequential access in splay trees takes linear time
• Dynamic Optimality—Almost

Cited in

(13)

• Experimental and Efficient Algorithms
• Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying
• Static optimality and dynamic search-optimality in lists and trees
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• In pursuit of the dynamic optimality conjecture
• scientific article; zbMATH DE number 7651167 (Why is no real title available?)
• Key-independent optimality
• On the deque conjecture for the splay algorithm
• scientific article; zbMATH DE number 7651207 (Why is no real title available?)
• Dynamic Optimality—Almost
• scientific article; zbMATH DE number 2119638 (Why is no real title available?)
• Sequential access in splay trees takes linear time
• A study on splay trees

This page was built for publication: A new path from Splay to dynamic optimality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236264)