- INSTANCE:
Directed acyclic graph
.
- SOLUTION:
Computation for
*G*that uses*k*registers, i.e., an ordering of the vertices in*V*and a sequence of subsets of*V*, each satisfying , such that is empty, contains all vertices with in-degree 0 in*G*, and, for , , , and contains all vertices*u*for which . - MEASURE:
Number of registers, i.e.,
*k*.

*Good News:*Approximable within [322].*Garey and Johnson:*PO1