Zobrazeno 1 - 10
of 296
pro vyhledávání: '"Munro, A. Ian"'
We use a novel decomposition to create succinct data structures -- supporting a wide range of operations on static trees in constant time -- for a variety tree classes, extending results of Munro, Nicholson, Benkner, and Wild. Motivated by the class
Externí odkaz:
http://arxiv.org/abs/2311.15511
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 distance between two vertices is the length of the shortest beer path.
Externí odkaz:
http://arxiv.org/abs/2209.14401
Publikováno v:
In Computational Geometry: Theory and Applications October 2024 122
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 covered by existing universal codes. At the same time, it supports answe
Externí odkaz:
http://arxiv.org/abs/2104.13457
Publikováno v:
ACM Transactions on Algorithms 18(1) (2022) 1-11
We present a simple $O(n^4)$-time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et al., has the same running time, but is significantly more complicated and is restricte
Externí odkaz:
http://arxiv.org/abs/2103.01084
Publikováno v:
Information and Computation 281 (2021)
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 one can precompute an optimal search tree, namely one that minimizes t
Externí odkaz:
http://arxiv.org/abs/2103.01052
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 the mapping between preorder (i.e., depth-first) ranks and level-orde
Externí odkaz:
http://arxiv.org/abs/2005.07644
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 stored on leaves, and intermediate nodes tracking the min of their respe
Externí odkaz:
http://arxiv.org/abs/1908.00563
For any $\epsilon \in (0,1)$, a $(1+\epsilon)$-approximate range mode query asks for the position of an element whose frequency in the query range is at most a factor $(1+\epsilon)$ smaller than the true mode. For this problem, we design an $O(n/\eps
Externí odkaz:
http://arxiv.org/abs/1907.08579