Chaitin's Algorithm (Global Register Allocation Register Allocation)
Revision as of 12:15, 15 February 2023 by Admin (talk | contribs) (Created page with "== 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 == Reference == https://dl.acm.org/doi/10.1145/872726.806984")
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