|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Succinct Choice Dictionaries | | Torben Hagerup
; Frank Kammer
; | | Date: |
20 Apr 2016 | | Abstract: | The choice dictionary is introduced as a data structure that can be
initialized with a parameter $ninmathbb{N}={1,2,ldots}$ and subsequently
maintains an initially empty subset $S$ of ${1,ldots,n}$ under insertion,
deletion, membership queries and an operation choice that returns an arbitrary
element of $S$. The choice dictionary appears to be fundamental in
space-efficient computing. We show that there is a choice dictionary that can
be initialized with $n$ and an additional parameter $tinmathbb{N}$ and
subsequently occupies $n+O(n(t/w)^t+log n)$ bits of memory and executes each
of the four operations insert, delete, contains (i.e., a membership query) and
choice in $O(t)$ time on a word RAM with a word length of $w=Omega(log n)$
bits. In particular, with $w=Theta(log n)$, we can support insert, delete,
contains and choice in constant time using $n+O(n/(log n)^t)$ bits for
arbitrary fixed $t$. We extend our results to maintaining several pairwise
disjoint subsets of ${1,ldots,n}$.
We study additional space-efficient data structures for subsets $S$ of
${1,ldots,n}$, including one that supports only insertion and an operation
extract-choice that returns and deletes an arbitrary element of $S$. All our
main data structures can be initialized in constant time and support efficient
iteration over the set $S$, and we can allow changes to $S$ while an iteration
over $S$ is in progress. We use these abilities crucially in designing the most
space-efficient algorithms known for solving a number of graph and other
combinatorial problems in linear time. In particular, given an undirected graph
$G$ with $n$ vertices and $m$ edges, we can output a spanning forest of $G$ in
$O(n+m)$ time with at most $(1+epsilon)n$ bits of working memory for arbitrary
fixed $epsilon>0$. | | Source: | arXiv, 1604.6058 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER