Register Allocation Via Coloring of Chordal Graphs

2005/01/01 by Fernando Magno Quintão Pereira, Jens Palsberg · 49 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Chordal graph #Compiler #Computer science #Formal Methods in Verification #Graph #Graph coloring #Heuristics #Iterated function #Mathematics #Parallel Computing and Optimization Techniques #Programming language #Register allocation #Theoretical computer science

paper · doi:10.1007/11575467_21

published in Lecture Notes in Computer Science, 315-329 (Springer Berlin Heidelberg)

crossref issued 2005/01/01 · crossref published 2005/01/01 · crossref published-print 2005/01/01 · openalex publication_date 2005/01/01 · crossref created 2005/11/11 · crossref deposited 2020/11/17 · openalex created_date 2025/10/10 · crossref indexed 2026/03/31 · openalex updated_date 2026/07/29

Citations

• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Recognizing Berge Graphs
• On rigid circuit graphs
• Improvements to graph coloring register allocation
• Register allocation & spilling via graph coloring
• Linear scan register allocation
• Iterated register coalescing
• Optimal spilling for CISC machines with few registers
• Register allocation & spilling via graph coloring

Cited by

• Greedy coloring [wikipedia]