# Questions tagged [succinct-data-structures]

The tag has no usage guidance.

8 questions
Filter by
Sorted by
Tagged with
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}$ ...
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|$ ...
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 ...
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 ...
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/...
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 ...