Chaitin's Algorithm (Global Register Allocation Register Allocation)
Jump to navigation
Jump to search
Time Complexity
$O(n^{2})$
Space Complexity
$O(n^{2})$ words
(Derived: this algorithm uses both an adjacency matrix (called the bit matrix) and adjacency lists (called the adjacency vectors))
Description
RIG coloring
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1981