Questions tagged [succinct-data-structures]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...