Dynamic Optimality—Almost

DOI10.1137/S0097539705447347MaRDI QIDQ5454250zbMATH OpenOpenAlexWikidataFDO

Authors Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu

Publication date 28 March 2008

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

competitivenessbinary search treessplay trees

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10)

Recommendations

• scientific article; zbMATH DE number 5237331
• In pursuit of the dynamic optimality conjecture
• The geometry of binary search trees
• A new path from Splay to dynamic optimality
• Static optimality and dynamic search-optimality in lists and trees

Cited in

(30)

• Demand-aware network designs of bounded degree
• Upper bounds for maximally greedy binary search trees
• On minimum generalized Manhattan connections
• Skip-Splay: Toward Achieving the Unified Bound in the BST Model
• Static optimality and dynamic search-optimality in lists and trees
• scientific article; zbMATH DE number 3317548 (Why is no real title available?)
• Competitive Online Search Trees on Trees
• scientific article; zbMATH DE number 7758335 (Why is no real title available?)
• scientific article; zbMATH DE number 1670671 (Why is no real title available?)
• In pursuit of the dynamic optimality conjecture
• ASA-graphs for efficient data representation and processing
• An \(O(\log \log n)\)-competitive binary search tree with optimal worst-case access times
• Competitive data-structure dynamization
• scientific article; zbMATH DE number 7651167 (Why is no real title available?)
• The envelope theorem in dynamic optimization
• Poketree: A Dynamically Competitive Data Structure with Good Worst-Case Performance
• A history of distribution-sensitive data structures
• Combining binary search trees
• Belga B-trees
• Arboral satisfaction: recognition and LP approximation
• scientific article; zbMATH DE number 7651207 (Why is no real title available?)
• A new path from Splay to dynamic optimality
• scientific article; zbMATH DE number 124845 (Why is no real title available?)
• The dynamic optimization of PKM
• scientific article; zbMATH DE number 2119638 (Why is no real title available?)
• The geometry of binary search trees
• A study on splay trees
• Better analysis of binary search tree on decomposable sequences
• Smooth heaps and a dual view of self-adjusting data structures
• Diameter estimates for graph associahedra

This page was built for publication: Dynamic Optimality—Almost

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