Questions tagged [succinct-data-structures]
The succinct-data-structures tag has no usage guidance.
8
questions
0
votes
0answers
19 views
What are the graph classes which takes logarithmic space in $|V|$ in circuit representation?
The $\text{SCR}$ representation of a graph $G=(V,E)$ is $C_{G}$ id the following conditions hold:
$C_{G}$ is a combinatorial circuit with memory.
$C_{G}$ has two inputs of length $n$ bits.
$C_{G}$ ...
-3
votes
1answer
43 views
Exponential amount of information in polynomial size? Impossible!
I'm reading A note on succinct representations of graphs by Papadimitriou and Yannakakis. Let me quote the following paragraph on page 183:
Formula $F$ has a highly regular structure. It has $|x|$ ...
2
votes
0answers
50 views
Storing relations space efficiently?
Let $f$ be a binary relation defined on set $S$, which contains numbers from $1$ to $n$. It is also given that number of $|\text{Img}(f)| \le k$. I want to store the function $f$ such in way such that ...
3
votes
1answer
126 views
Compact mapping from an involuted set
Let $S$ be a set (say positive integers $\leq$ N) and $f$ an involution ($f$ is bijective, $f\cdot f=id$, e.g. xor with a constant). $g$ is a idempotent mapping choosing an arbitrary representative ...
4
votes
1answer
97 views
Looking for a succinct dynamic sorted dictionary
I was digging through research articles to find a data structure that solves the dynamic sorted dictionary problem (representing any subset $S$ of a universe $U = \{0, \ldots, u\}$ with member/...
4
votes
2answers
76 views
Succinct data structure to return occurences of letters until an index
I want to try and use a succinct type data structure in order to find the amount of occurences of a letter $C$ in a string $S$ until a given index $I$.
Assume we have a string $S$ of length $n$ over ...
1
vote
1answer
158 views
Heap-like notation of a BST (BFT bit-vectors) for succinct representation
I'm researching the topic of succinct tree representations right now and came across this presentation. On slide 17 there is an example of heap-like notation of a BST (using BFT bit-vectors) and the ...
3
votes
0answers
251 views
Generalization of XOR Linked Lists
Are there any results generalizing XOR Linked Lists to other types of data structures?
For example, just like an XOR Linked List requires two pointers and can iterate a 1 dimensional list, I can ...
