8 citations · 32 across the 18 of their papers we have counts for
25 papers
Shortest Beer Path Queries in Interval Graphs
Rathish Das, Meng He, Eitan Kondratovsky +3
Our interest is in paths between pairs of vertices that go through at least one of a subset of the vertices known as beer vertices. Such a path is called a beer path, and the beer…
Hypersuccinct Trees -- New universal tree source codes for optimal compressed tree data structures and range minima
J. Ian Munro, Patrick K. Nicholson, Louisa Seelbach Benkner +1
We present a new universal source code for distributions of unlabeled binary and ordinal trees that achieves optimal compression to within lower order terms for all tree sources co…
On the Cost of Unsuccessful Searches in Search Trees with Two-way Comparisons
Marek Chrobak, Mordecai Golin, J. Ian Munro +1
Search trees are commonly used to implement access operations to a set of stored keys. If this set is static and the probabilities of membership queries are known in advance, then…
A Simple Algorithm for Optimal Search Trees with Two-Way Comparisons
Marek Chrobak, Mordecai Golin, J. Ian Munro +1
We present a simple -time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et al., has the sam…
Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees
Meng He, J. Ian Munro, Yakov Nekrich +2
We present the first succinct distance oracles for (unweighted) interval graphs and related classes of graphs, using a novel succinct data structure for ordinal trees that supports…
Dynamic Optimality Refuted -- For Tournament Heaps
J. Ian Munro, Richard Peng, Sebastian Wild +1
We prove a separation between offline and online algorithms for finger-based tournament heaps undergoing key modifications. These heaps are implemented by binary trees with keys st…