{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T10:09:54Z","timestamp":1777889394968,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642370502","type":"print"},{"value":"9783642370519","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-37051-9_1","type":"book-chapter","created":{"date-parts":[[2013,2,18]],"date-time":"2013-02-18T19:35:47Z","timestamp":1361216147000},"page":"1-20","source":"Crossref","is-referenced-by-count":16,"title":["Optimal Register Allocation in Polynomial Time"],"prefix":"10.1007","author":[{"given":"Philipp Klaus","family":"Krause","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","unstructured":"Coremark, \n                    \n                      http:\/\/www.coremark.org"},{"key":"1_CR2","unstructured":"Guidelines for the Use of the C Language in Critical Systems (MISRA-C:2004, 2nd Edition). Technical report, MISRA (2008)"},{"issue":"6","key":"1_CR3","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal of Computation\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM Journal of Computation"},{"key":"1_CR4","unstructured":"Bodlaender, H.L., Gustedt, J., Telle, J.A.: Linear-Time Register Allocation for a Fixed Number of Registers. In: SODA 1998: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 574\u2013583. Society for Industrial and Applied Mathematics (1998)"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Bouchez, F., Darte, A., Rastello, F.: On the Complexity of Register Coalescing. In: Proceedings of the International Symposium on Code Generation and Optimization, CGO 2007, pp. 102\u2013114. IEEE Computer Society (2007)","DOI":"10.1109\/CGO.2007.26"},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-24841-5_6","volume-title":"Reliable Software Technologies - Ada-Europe 2004","author":"B. Burgstaller","year":"2004","unstructured":"Burgstaller, B., Blieberger, J., Scholz, B.: On the Tree Width of Ada Programs. In: Llamos\u00ed, A., Strohmeier, A. (eds.) Ada-Europe 2004. LNCS, vol.\u00a03063, pp. 78\u201390. Springer, Heidelberg (2004)"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Chaitin, G.J.: Register allocation & spilling via graph coloring. In: SIGPLAN 1982: Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction, pp. 98\u2013105. Association for Computing Machinery (1982)","DOI":"10.1145\/800230.806984"},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0096-0551(81)90048-5","volume":"6","author":"G.J. Chaitin","year":"1981","unstructured":"Chaitin, G.J., Auslander, M.A., Chandra, A.K., Cocke, J., Hopkins, M.E., Markstein, P.W.: Register allocation via coloring. Computer Languages\u00a06, 47\u201357 (1981)","journal-title":"Computer Languages"},{"key":"1_CR9","unstructured":"ChaN. Fatfs, \n                    \n                      http:\/\/elm-chan.org\/fsw\/ff\/00index_e.html"},{"issue":"1-2","key":"1_CR10","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0304-3975(96)00177-6","volume":"172","author":"N.D. Dendris","year":"1997","unstructured":"Dendris, N.D., Kirousis, L.M., Thilikos, D.M.: Fugitive-search games on graphs and related parameters. Theoretical Computer Science\u00a0172(1-2), 233\u2013254 (1997)","journal-title":"Theoretical Computer Science"},{"key":"1_CR11","unstructured":"Dunkels, A., Gr\u00f6nvall, B., Voigt, T.: Contiki - a Lightweight and Flexible Operating System for Tiny Networked Sensors. In: Proceedings of the First IEEE Workshop on Embedded Networked Sensors (Emnets-I) (November 2004)"},{"key":"1_CR12","first-page":"30","volume":"121","author":"S. Dutta","year":"2000","unstructured":"Dutta, S.: Anatomy of a Compiler. Circuit Cellar\u00a0121, 30\u201335 (2000)","journal-title":"Circuit Cellar"},{"key":"1_CR13","unstructured":"Evlogimenos, A.: Improvements to Linear Scan register allocation, Technical report, University of Illinois, Urbana-Champaign (2004)"},{"key":"1_CR14","unstructured":"Farach, M., Liberatore, V.: On local register allocation. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1998, pp. 564\u2013573. Society for Industrial and Applied Mathematics (1998)"},{"key":"1_CR15","unstructured":"Fu, C., Wilken, K.: A Faster Optimal Register Allocator. In: MICRO 35: Proceedings of the 35th Annual ACM\/IEEE International Symposium on Microarchitecture, pp. 245\u2013256. IEEE Computer Society Press (2002)"},{"issue":"2","key":"1_CR16","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M.R. Garey","year":"1980","unstructured":"Garey, M.R., Johnson, D.S., Miller, G.L., Papadimitriou, C.H.: The Complexity of Coloring Circular Arcs and Chords. SIAM Journal on Algebraic Discrete Methods\u00a01(2), 216\u2013227 (1980)","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"issue":"8","key":"1_CR17","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1002\/(SICI)1097-024X(199608)26:8<929::AID-SPE40>3.0.CO;2-T","volume":"26","author":"D.W. Goodwin","year":"1996","unstructured":"Goodwin, D.W., Wilken, K.D.: Optimal and near-optimal global register allocations using 0\u20131 integer programming. Software Practice & Experience\u00a026(8), 929\u2013965 (1996)","journal-title":"Software Practice & Experience"},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-642-03685-9_13","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"V. Guruswami","year":"2009","unstructured":"Guruswami, V., Sinop, A.K.: Improved Inapproximability Results for Maximum k-Colorable Subgraph. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol.\u00a05687, pp. 163\u2013176. Springer, Heidelberg (2009)"},{"key":"1_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/3-540-45643-0_7","volume-title":"Algorithm Engineering and Experiments","author":"J. Gustedt","year":"2002","unstructured":"Gustedt, J., M\u00e6hle, O.A., Telle, J.A.: The Treewidth of Java Programs. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol.\u00a02409, pp. 86\u201397. Springer, Heidelberg (2002)"},{"key":"1_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/11688839_20","volume-title":"Compiler Construction","author":"S. Hack","year":"2006","unstructured":"Hack, S., Grund, D., Goos, G.: Register Allocation for Programs in SSA-Form. In: Mycroft, A., Zeller, A. (eds.) CC 2006. LNCS, vol.\u00a03923, pp. 247\u2013262. Springer, Heidelberg (2006)"},{"issue":"1","key":"1_CR21","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/BF01351673","volume":"172","author":"R. Halin","year":"1967","unstructured":"Halin, R.: Zur Klassifikation der endlichen Graphen nach H. Hadwiger und K. Wagner. Mathematische Annalen\u00a0172(1), 46\u201378 (1967)","journal-title":"Mathematische Annalen"},{"key":"1_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/11860990_21","volume-title":"Modular Programming Languages","author":"L. Hames","year":"2006","unstructured":"Hames, L., Scholz, B.: Nearly Optimal Register Allocation with PBQP. In: Lightfoot, D.E., Ren, X.-M. (eds.) JMLC 2006. LNCS, vol.\u00a04228, pp. 346\u2013361. Springer, Heidelberg (2006)"},{"key":"1_CR23","unstructured":"Kannan, S., Proebsting, T.: Register Allocation in Structured Programs. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995, pp. 360\u2013368. Society for Industrial and Applied Mathematics (1995)"},{"key":"1_CR24","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"R.M. Karp","year":"1975","unstructured":"Karp, R.M.: On the Computational Complexity of Combinatorial Problems. Networks\u00a05, 45\u201368 (1975)","journal-title":"Networks"},{"key":"1_CR25","unstructured":"Krause, P.K.: The Complexity of Register Allocation. To appear in the GROW 2011 special issue of Discrete Applied Mathematics (2011)"},{"issue":"1-3","key":"1_CR26","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/j.tcs.2008.05.025","volume":"407","author":"J.K. Lee","year":"2008","unstructured":"Lee, J.K., Palsberg, J., Pereira, F.M.Q.: Aliased register allocation for straight-line programs is NP-complete. Theoretical Computer Science\u00a0407(1-3), 258\u2013273 (2008)","journal-title":"Theoretical Computer Science"},{"key":"1_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/11575467_21","volume-title":"Programming Languages and Systems","author":"F.M.Q. Pereira","year":"2005","unstructured":"Pereira, F.M.Q.: Register Allocation Via Coloring of Chordal Graphs. In: Yi, K. (ed.) APLAS 2005. LNCS, vol.\u00a03780, pp. 315\u2013329. Springer, Heidelberg (2005)"},{"issue":"5","key":"1_CR28","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1145\/330249.330250","volume":"21","author":"M. Poletto","year":"1999","unstructured":"Poletto, M., Sarkar, V.: Linear scan register allocation. ACM Transactions on Programming Languages and Systems (TOPLAS)\u00a021(5), 895\u2013913 (1999)","journal-title":"ACM Transactions on Programming Languages and Systems (TOPLAS)"},{"issue":"1","key":"1_CR29","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors. I. Excluding a Forest. Journal of Combinatorial Theory, Series B\u00a035(1), 39\u201361 (1983)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"7","key":"1_CR30","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1145\/566225.513854","volume":"37","author":"B. Scholz","year":"2002","unstructured":"Scholz, B., Eckstein, E.: Register Allocation for Irregular Architectures. SIGPLAN Notices\u00a037(7), 139\u2013148 (2002)","journal-title":"SIGPLAN Notices"},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"Smith, M.D., Ramsey, N., Holloway, G.: A Generalized Algorithm for Graph-Coloring Register Allocation. In: PLDI 2004: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, pp. 277\u2013288. Association for Computing Machinery (2004)","DOI":"10.1145\/996841.996875"},{"issue":"2","key":"1_CR32","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1006\/inco.1997.2697","volume":"142","author":"M. Thorup","year":"1998","unstructured":"Thorup, M.: All Structured Programs Have Small Tree Width and Good Register Allocation. Information and Computation\u00a0142(2), 159\u2013181 (1998)","journal-title":"Information and Computation"},{"key":"1_CR33","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1145\/358274.358283","volume":"27","author":"R.P. Weicker","year":"1984","unstructured":"Weicker, R.P.: Dhrystone: a synthetic systems programming benchmark. Communications of the ACM\u00a027, 1013\u20131030 (1984)","journal-title":"Communications of the ACM"},{"key":"1_CR34","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1145\/47907.47911","volume":"23","author":"R.P. Weicker","year":"1988","unstructured":"Weicker, R.P.: Dhrystone Benchmark: Rationale for Version 2 and Measurement Rules. SIGPLAN Notices\u00a023, 49\u201362 (1988)","journal-title":"SIGPLAN Notices"},{"issue":"2","key":"1_CR35","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(87)90107-4","volume":"24","author":"M. Yannakakis","year":"1987","unstructured":"Yannakakis, M., Gavril, F.: The maximum k-colorable subgraph problem for chordal graphs. Information Processing Letters\u00a024(2), 133\u2013137 (1987)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Compiler Construction"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-37051-9_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,11]],"date-time":"2019-05-11T08:15:10Z","timestamp":1557562510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-37051-9_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642370502","9783642370519"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-37051-9_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}