Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM REGISTER SUFFICIENCY

• INSTANCE: Directed acyclic graph $G=\left(V,E\right)$.

• SOLUTION: Computation for G that uses k registers, i.e., an ordering $v_1, \ldots, v_n$ of the vertices in V and a sequence $S_0, \ldots, S_n$ of subsets of V, each satisfying $\vert S_i\vert \leq k$, such that $S_0$ is empty, $S_n$ contains all vertices with in-degree 0 in G, and, for $1 \leq i \leq n$, $v_i \in S_i$, $S_i - \{v_i\} \subseteq S_{i-1}$, and $S_{i-1}$ contains all vertices u for which $(v_i,u) \in A$.

• MEASURE: Number of registers, i.e., k.

  
  

• Good News: Approximable within $O(\log^2 n)$ [322].

• Garey and Johnson: PO1