Chaitin's Algorithm (Global Register Allocation Register Allocation)

From Algorithm Wiki
Revision as of 11: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.ezproxy.canberra.edu.au/doi/10.1145/872726.806984")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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

Reference

https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/872726.806984

Retrieved from "https://algorithm-wiki-csail-mit-edu.ezproxy.canberra.edu.au/w/index.php?title=Chaitin%27s_Algorithm_(Global_Register_Allocation_Register_Allocation)&oldid=45371"