A new path from Splay to dynamic optimality

DOI10.1137/1.9781611975482.80zbMATH Open1431.68023OpenAlexW4255385822MaRDI QIDQ5236264FDOQ5236264

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

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

Mathematics Subject Classification ID

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

Cited In (13)

• 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
• Title not available (Why is that?)
• Key-independent optimality
• On the deque conjecture for the splay algorithm
• Title not available (Why is that?)
• Dynamic Optimality—Almost
• Title not available (Why is that?)
• Sequential access in splay trees takes linear time
• A study on splay trees
• Experimental and Efficient Algorithms

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)