{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T03:46:15Z","timestamp":1772163975843,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":21,"publisher":"ACM","license":[{"start":{"date-parts":[[2007,6,13]],"date-time":"2007-06-13T00:00:00Z","timestamp":1181692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2007,6,13]]},"DOI":"10.1145\/1254766.1254782","type":"proceedings-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T12:07:37Z","timestamp":1189771657000},"page":"103-112","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["On the complexity of spill everywhere under SSA form"],"prefix":"10.1145","author":[{"given":"Florent","family":"Bouchez","sequence":"first","affiliation":[{"name":"LIP: CNRS -- ENS Lyon -- UCB Lyon -- INRIA, Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alain","family":"Darte","sequence":"additional","affiliation":[{"name":"LIP: CNRS -- ENS Lyon -- UCB Lyon -- INRIA, Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrice","family":"Rastello","sequence":"additional","affiliation":[{"name":"LIP: CNRS -- ENS Lyon -- UCB Lyon -- INRIA, Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378854"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"e_1_3_2_1_3_1","volume-title":"North Holland","author":"Berge C.","year":"1973","unstructured":"C. Berge . Graphs and Hypergraphs . North Holland , 1973 . C. Berge. Graphs and Hypergraphs. North Holland, 1973."},{"key":"e_1_3_2_1_5_1","volume-title":"International Workshop on Languages and Compilers for Parallel Computing (LCPC'06)","author":"Bouchez Florent","year":"2006","unstructured":"Florent Bouchez , Alain Darte , Christophe Guillon , and Fabrice Rastello . Register allocation : What does the NP-completeness proof of Chaitin et al. really prove? In International Workshop on Languages and Compilers for Parallel Computing (LCPC'06) , LNCS, New Orleans, Louisiana , 2006 . Springer Verlag. Florent Bouchez, Alain Darte, Christophe Guillon, and Fabrice Rastello. Register allocation: What does the NP-completeness proof of Chaitin et al. really prove? In International Workshop on Languages and Compilers for Parallel Computing (LCPC'06), LNCS, New Orleans, Louisiana, 2006. Springer Verlag."},{"key":"e_1_3_2_1_6_1","volume-title":"14th International Workshop on Logic and Synthesis","author":"Brisk Philip","year":"2005","unstructured":"Philip Brisk , Foad Dabiri , Jamie Macbeth , and Majid Sarrafzadeh . Polynomial time graph coloring register allocation . In 14th International Workshop on Logic and Synthesis , June 2005 . Philip Brisk, Foad Dabiri, Jamie Macbeth, and Majid Sarrafzadeh. Polynomial time graph coloring register allocation. In 14th International Workshop on Logic and Synthesis, June 2005."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512534"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2245737.2245881"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2006.35"},{"key":"e_1_3_2_1_10_1","volume-title":"Morgan Kaufmann","author":"Keith","year":"2004","unstructured":"Keith D. Cooper and Linda Torczon. Engineering a Compiler . Morgan Kaufmann , 2004 . Keith D. Cooper and Linda Torczon. Engineering a Compiler. Morgan Kaufmann, 2004."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1095"},{"key":"e_1_3_2_1_12_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and Davis S. Johnson . Computers and Intractability: A Guide to the Theory of NP-Completeness . W.H. Freeman and Company , 1979 . Michael R. Garey and Davis S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979."},{"key":"e_1_3_2_1_13_1","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic Martin Charles","year":"1980","unstructured":"Martin Charles Golumbic . Algorithmic Graph Theory and Perfect Graphs . Academic Press , New York , 1980 . Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980."},{"key":"e_1_3_2_1_14_1","volume-title":"International Workshop on Languages and Compilers for Parallel Computing (LCPC'06)","author":"Grothoff Christian","year":"2006","unstructured":"Christian Grothoff , Rajkishore Barik , Rahul Gupta , and Vinayaka Pandit . Optimal bitwise register allocation using integer linear programming . In International Workshop on Languages and Compilers for Parallel Computing (LCPC'06) , LNCS, New Orleans, Louisiana , 2006 . Springer Verlag. Christian Grothoff, Rajkishore Barik, Rahul Gupta, and Vinayaka Pandit. Optimal bitwise register allocation using integer linear programming. In International Workshop on Languages and Compilers for Parallel Computing (LCPC'06), LNCS, New Orleans, Louisiana, 2006. Springer Verlag."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.01.008"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_20"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/353926.353929"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/330249.330250"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277714"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064979.1064998"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804355"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90107-4"}],"event":{"name":"LCTES 07: ACM SIGBED-SIGPLAN Conference on Languages, Compilers and Tools for Embedded Systems","location":"San Diego California USA","acronym":"LCTES 07","sponsor":["SIGPLAN ACM Special Interest Group on Programming Languages","ACM Association for Computing Machinery","SIGBED ACM Special Interest Group on Embedded Systems","SIGDA ACM Special Interest Group on Design Automation","SIGARCH ACM Special Interest Group on Computer Architecture","SIGMICRO ACM Special Interest Group on Microarchitectural Research and Processing"]},"container-title":["Proceedings of the 2007 ACM SIGPLAN\/SIGBED conference on Languages, compilers, and tools for embedded systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1254766.1254782","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1254766.1254782","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:47:48Z","timestamp":1750243668000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1254766.1254782"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6,13]]},"references-count":21,"alternative-id":["10.1145\/1254766.1254782","10.1145\/1254766"],"URL":"https:\/\/doi.org\/10.1145\/1254766.1254782","relation":{"is-identical-to":[{"id-type":"doi","id":"10.1145\/1273444.1254782","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2007,6,13]]},"assertion":[{"value":"2007-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}