11 papers
Towards the 5/6-Density Conjecture of Pinwheel Scheduling
Leszek Gąsieniec, Benjamin Smith, Sebastian Wild
Pinwheel Scheduling aims to find a perpetual schedule for unit-length tasks on a single machine subject to given maximal time spans (a.k.a. frequencies) between any two consecutive…
Succinct Euler-Tour Trees
Travis Gagie, Sebastian Wild
We show how a collection of Euler-tour trees for a forest on vertices can be stored in bits such that simple queries take constant time, more complex queries take…
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…
Lazy Search Trees
Bryce Sandlund, Sebastian Wild
We introduce the lazy search tree data structure. The lazy search tree is a comparison-based data structure on the pointer machine that supports order-based operations such as rank…
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…
Efficient Second-Order Shape-Constrained Function Fitting
David Durfee, Yu Gao, Anup B. Rao +1
We give an algorithm to compute a one-dimensional shape-constrained function that best fits given data in weighted- norm. We give a single algorithm that works for a va…