research
∙
09/28/2022
Shortest Beer Path Queries in Interval Graphs
Our interest is in paths between pairs of vertices that go through at le...
share
research
∙
04/27/2021
Hypersuccinct Trees – New universal tree source codes for optimal compressed tree data structures
We present a new universal source code for unlabeled binary and ordinal ...
research
∙
03/01/2021
A Simple Algorithm for Optimal Search Trees with Two-Way Comparisons
We present a simple O(n^4)-time algorithm for computing optimal search t...
research
∙
03/01/2021
On the Cost of Unsuccessful Searches in Search Trees with Two-way Comparisons
Search trees are commonly used to implement access operations to a set o...
research
∙
05/15/2020
Breadth-First Rank/Select in Succinct Trees and Distance Oracles for Interval Graphs
We present the first succinct data structure for ordinal trees that supp...
research
∙
08/01/2019
Dynamic Optimality Refuted -- For Tournament Heaps
We prove a separation between offline and online algorithms for finger-b...
research
∙
07/19/2019
On Approximate Range Mode and Range Selection
For any ϵ∈ (0,1), a (1+ϵ)-approximate range mode query asks for the posi...
research
∙
03/15/2019
Dynamic Planar Point Location in External Memory
In this paper we describe a fully-dynamic data structure for the planar ...
research
∙
03/06/2019
Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space
The range-minimum query (RMQ) problem is a fundamental data structuring ...
research
∙
02/13/2019
Space-Efficient Data Structures for Lattices
A lattice is a partially-ordered set in which every pair of elements has...
research
∙
01/12/2019
On Huang and Wong's Algorithm for Generalized Binary Split Trees
Huang and Wong [5] proposed a polynomial-time dynamic-programming algori...
research
∙
07/10/2018
Improved Time and Space Bounds for Dynamic Range Mode
Given an array A of n elements, we wish to support queries for the most ...
research
∙
06/27/2018
Dynamic Trees with Almost-Optimal Access Cost
An optimal binary search tree for an access sequence on elements is a st...
research
∙
05/10/2018
Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs
We present two stable mergesort variants, "peeksort" and "powersort", th...
research
∙
12/20/2017