Multi-Finger Binary Search Trees

DOI10.4230/LIPIcs.ISAAC.2018.55OpenAlexW2892208052MaRDI QIDQ5091047

László Kozma, Parinya Chalermsook, Thatchaphol Saranurak, Kurt Mehlhorn, Mayank Goswami

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1809.01759

zbMATH Keywords

binary search treesdynamic optimalityfinger search\(k\)-server

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pattern matching for permutations
• The \(k\)-server problem
• The power and limitations of static binary search trees with lazy finger
• Confluently persistent tries for efficient version control
• A new data structure for representing sorted lists
• Sorting shuffled monotone sequences
• Competitive \(k\)-server algorithms
• Static optimality and dynamic search-optimality in lists and trees
• Asymptotic values for degrees associated with strips of Young diagrams
• Randomized search trees
• A unified access bound on comparison-based dynamic dictionaries
• Efficient algorithms for online decision problems
• In Pursuit of the Dynamic Optimality Conjecture
• A Polylogarithmic-Competitive Algorithm for the k -Server Problem
• Skip-Splay: Toward Achieving the Unified Bound in the BST Model
• An Optimal On-Line Algorithm for K Servers on Trees
• Self-Adjusting Binary Search Trees: What Makes Them Tick?
• Competitive algorithms for server problems
• Design and Analysis of a Data Structure for Representing Sorted Lists
• On the k -server conjecture
• On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• Weighted dynamic finger in binary search trees
• Combining Binary Search Trees
• The harmonic k -server algorithm is competitive
• Algorithms and Data Structures