6 citations · 10 across the 13 of their papers we have counts for
6 papers · 1 filter
Fragile Complexity of Adaptive Algorithms
Prosenjit Bose, Pilar Cano, Rolf Fagerberg +3
The fragile complexity of a comparison-based algorithm is if each input element participates in comparisons. In this paper, we explore the fragile complexity of al…
Fragile Complexity of Comparison-Based Algorithms
Peyman Afshani, Rolf Fagerberg, David Hammer +5
We initiate a study of algorithms with a focus on the computational complexity of individual elements, and introduce the fragile complexity of comparison-based algorithms as the ma…
Biased Predecessor Search
Prosenjit Bose, Rolf Fagerberg, John Howat +1
We consider the problem of performing predecessor searches in a bounded universe while achieving query times that depend on the distribution of queries. We obtain several data stru…
De-amortizing Binary Search Trees
Prosenjit Bose, Sébastien Collette, Rolf Fagerberg +1
We present a general method for de-amortizing essentially any Binary Search Tree (BST) algorithm. In particular, by transforming Splay Trees, our method produces a BST that has the…
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…
Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts
Philip Bille, Rolf Fagerberg, Inge Li Goertz
We study the approximate string matching and regular expression matching problem for the case when the text to be searched is compressed with the Ziv-Lempel adaptive dictionary com…