Dynamic Optimality—Almost

DOI10.1137/S0097539705447347zbMATH Open1142.68025OpenAlexW2017619076WikidataQ56060743 ScholiaQ56060743MaRDI QIDQ5454250FDOQ5454250

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

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

zbMATH Keywords

competitivenessbinary search treessplay trees

Mathematics Subject Classification ID

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

Cited In (30)

• Upper bounds for maximally greedy binary search trees
• Skip-Splay: Toward Achieving the Unified Bound in the BST Model
• On minimum generalized Manhattan connections
• Static optimality and dynamic search-optimality in lists and trees
• Title not available (Why is that?)
• Competitive Online Search Trees on Trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• A new path from Splay to dynamic optimality
• Title not available (Why is that?)
• The dynamic optimization of PKM
• Title not available (Why is that?)
• 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
• Demand-aware network designs of bounded degree

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)