Aliased register allocation for straight-line programs is NP-complete

DOI10.1016/j.tcs.2008.05.025zbMath1160.68015OpenAlexW2035698180MaRDI QIDQ954999

Jens Palsberg, Fernando Magno Quintão Pereira, Jonathan K. Lee

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.05.025

zbMATH Keywords

graph coloringnetwork flowregister allocationweighted interval graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

On minimizing register usage of linearly scheduled algorithms with uniform dependencies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
• Optimal parallel time bounds for the maximum clique problem on intervals
• Precoloring extension. I: Interval graphs
• Algorithmic graph theory and perfect graphs
• A Framework for End-to-End Verification and Evaluation of Register Allocators
• On the Complexity of Timetable and Multicommodity Flow Problems
• Modern Compiler Implementation in Java

This page was built for publication: Aliased register allocation for straight-line programs is NP-complete