Competitive Online Search Trees on Trees
From MaRDI portal
Publication:6051990
DOI10.1145/3595180OpenAlexW2966205006MaRDI QIDQ6051990
Prosenjit Bose, Grigorios Koumoutsos, Stefan Langerman, John Iacono, Jean Cardinal
Publication date: 23 October 2023
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3595180
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Mathematical Theory of Communication
- On the tree search problem with non-uniform costs
- Sparsity. Graphs, structures, and algorithms
- Improved approximation algorithms for the average-case tree searching problem
- On the complexity of searching in trees and partially ordered structures
- The power and limitations of static binary search trees with lazy finger
- Graph properties of graph associahedra
- Faces of generalized permutohedra
- Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying
- Nearly optimal binary search trees
- Finding minimum height elimination trees for interval graphs in polynomial time
- The associahedron and triangulations of the \(n\)-gon
- Optimal node ranking of tree in linear time
- A data structure for dynamic trees
- On the vertex ranking problem for trapezoid, circular-arc and other graphs
- On the diameter of tree associahedra
- Many non-equivalent realizations of the associahedron
- The diameter of associahedra
- Coxeter complexes and graph-associahedra
- Optimum binary search trees
- In Pursuit of the Dynamic Optimality Conjecture
- Self-Adjusting Binary Search Trees: What Makes Them Tick?
- O(log log n)-competitive dynamic binary search trees
- Permutohedra, Associahedra, and Beyond
- Self-adjusting binary search trees
- Lower Bounds for Accessing Binary Search Trees with Rotations
- A Best Possible Bound for The Weighted Path Length of Binary Search Trees
- Optimal Search in Trees
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Rankings of Graphs
- 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
- Generalized Template Splay: A Basic Theory and Calculus
- An Explanation of Splaying
- Searching in Dynamic Tree-Like Partial Orders
- Deterministic and probabilistic binary search in graphs
- Dynamic Optimality—Almost
- Homotopy Associativity of H-Spaces. I
- Monoïdes préordonnés et chaînes de Malcev
