83 citations · 606 across the 54 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2010★ 6 cited
An O(loglog n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times
Prosenjit Bose, Karim Douïeb, Vida Dujmovic +1
We present the zipper tree, an -competitive online binary search tree that performs each access in worst-case time. This shows that for binary search tr…
cs.DS2009★ 17 cited
Notes on large angle crossing graphs
Vida Dujmovic, Joachim Gudmundsson, Pat Morin +1
A graph G is an a-angle crossing (aAC) graph if every pair of crossing edges in G intersect at an angle of at least a. The concept of right angle crossing (RAC) graphs (a=Pi/2) was…
cs.DS2009
Layered Working-Set Trees
Prosenjit Bose, Karim Douïeb, Vida Dujmović +1
The working-set bound [Sleator and Tarjan, J. ACM, 1985] roughly states that searching for an element is fast if the element was accessed recently. Binary search trees, such as spl…