W. Andrew, L. Appel, and . George, Optimal spilling for CISC machines with few registers, ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'01), pp.243-253, 2001.

L. A. Belady, A study of replacement algorithms for a virtual-storage computer, IBM Systems Journal, vol.5, issue.2, pp.78-101, 1966.
DOI : 10.1147/sj.52.0078

C. Berge, Graphs and Hypergraphs, 1973.

F. Bouchez, A. Darte, C. Guillon, and F. Rastello, Register allocation and spill complexity under SSA, 2005.

F. Bouchez, A. Darte, C. Guillon, and F. Rastello, Register allocation: What does the NP-completeness proof of Chaitin et al. really prove?, International Workshop on Languages and Compilers for Parallel Computing (LCPC'06), 2006.

P. Brisk, F. Dabiri, J. Macbeth, and M. Sarrafzadeh, Polynomial time graph coloring register allocation, 14th International Workshop on Logic and Synthesis, 2005.

Z. Budimli´cbudimli´c, K. Cooper, T. Harvey, K. Kennedy, T. Oberg et al., Fast copy coalescing and live range identification, ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'02), pp.25-32, 2002.

G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins et al., Register allocation via coloring, Computer Languages, vol.6, issue.1, pp.47-57, 1981.
DOI : 10.1016/0096-0551(81)90048-5

D. Keith, A. Cooper, and . Dasgupta, Tailoring graph-coloring register allocation for runtime compilation, International Symposium on Code Generation and Optimization (CGO'06), pp.39-49, 2006.

D. Keith, L. Cooper, and . Torczon, Engineering a Compiler, 2004.

M. Farach-colton and V. Liberatore, On Local Register Allocation, Journal of Algorithms, vol.37, issue.1, pp.37-65, 2000.
DOI : 10.1006/jagm.2000.1095

R. Michael, D. S. Garey, and . Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

M. Charles and G. , Algorithmic Graph Theory and Perfect Graphs, 1980.

C. Grothoff, R. Barik, R. Gupta, and V. Pandit, Optimal bitwise register allocation using integer linear programming, International Workshop on Languages and Compilers for Parallel Computing (LCPC'06), 2006.

S. Hack and G. Goos, Optimal register allocation for SSA-form programs in polynomial time, Information Processing Letters, vol.98, issue.4, pp.150-155, 2006.
DOI : 10.1016/j.ipl.2006.01.008

S. Hack, D. Grund, and G. Goos, Towards register allocation for programs in SSA-form, 2005.

S. Hack, D. Grund, and G. Goos, Register Allocation for Programs in SSA-Form, International Conference on Compiler Construction, 2006.
DOI : 10.1007/11688839_20

T. Guei-yuan-lueh, A. Gross, and . Adl-tabatabai, Fusion-based register allocation, ACM Transactions on Programming Languages and Systems, vol.22, issue.3, pp.431-470, 2000.
DOI : 10.1145/353926.353929

S. Poletto, Linear scan register allocation, ACM Transactions on Programming Languages and Systems, vol.21, issue.5, pp.895-913, 1999.
DOI : 10.1145/330249.330250

O. Traub, G. H. Holloway, and M. D. Smith, Quality and speed in linear-scan register allocation, ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'98), pp.142-151, 1998.

C. Wimmer and H. Mössenböck, Optimized interval splitting in a linear scan register allocator, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments , VEE '05, 2005.
DOI : 10.1145/1064979.1064998

M. Yannakakis, Node-and edge-deletion NP-complete problems, Proceedings of the tenth annual ACM symposium on Theory of computing , STOC '78, pp.253-264, 1978.
DOI : 10.1145/800133.804355

M. Yannakakis and F. Gavril, The maximum k-colorable subgraph problem for chordal graphs, Information Processing Letters, vol.24, issue.2, pp.133-137, 1987.
DOI : 10.1016/0020-0190(87)90107-4