Next: MINIMUM LOCAL REGISTER ALLOCATION
Up: Code Generation
Previous: Code Generation
  Index
- 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
Viggo Kann
2000-03-20