Questions tagged [succinct-data-structures]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
18 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
42 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
47 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
119 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 ...
3
votes
1answer
92 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
75 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
132 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
245 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 ...