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

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

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

(17)

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

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)