{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T12:59:10Z","timestamp":1790859550755,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540297352","type":"print"},{"value":"9783540322474","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11575467_21","type":"book-chapter","created":{"date-parts":[[2005,11,11]],"date-time":"2005-11-11T08:58:51Z","timestamp":1131699531000},"page":"315-329","source":"Crossref","is-referenced-by-count":52,"title":["Register Allocation Via Coloring of Chordal Graphs"],"prefix":"10.1007","author":[{"given":"Fernando Magno Quint\u00e3o","family":"Pereira","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens","family":"Palsberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"21_CR1","first-page":"34","volume-title":"12th Conference on Compiler Construction","author":"C. Andersson","year":"2003","unstructured":"Andersson, C.: Register allocation by optimal graph coloring. In: 12th Conference on Compiler Construction, pp. 34\u201345. Springer, Heidelberg (2003)"},{"key":"21_CR2","first-page":"243","volume-title":"International Conference on Programming Languages Design and Implementation","author":"A.W. Appel","year":"2001","unstructured":"Appel, A.W., George, L.: Optimal spilling for cisc machines with few registers. In: International Conference on Programming Languages Design and Implementation, pp. 243\u2013253. ACM Press, New York (2001)"},{"key":"21_CR3","unstructured":"Appel, A.W., George, L.: 27,921 actual register-interference graphs generated by standard ML of New Jersey, version 1.09 (2005), http:\/\/www.cs.princeton.edu\/~appel\/graphdata\/"},{"issue":"4","key":"21_CR4","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/s00453-004-1084-3","volume":"39","author":"A. Berry","year":"2004","unstructured":"Berry, A., Blair, J., Heggernes, P., Peyton, B.: Maximum cardinality search for computing minimal triangulations of graphs. Algorithmica\u00a039(4), 287\u2013298 (2004)","journal-title":"Algorithmica"},{"issue":"3","key":"21_CR5","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1145\/177492.177575","volume":"16","author":"P. Briggs","year":"1994","unstructured":"Briggs, P., Cooper, K.D., Torczon, L.: Improvements to graph coloring register allocation. Transactions on Programming Languages and Systems (TOPLAS)\u00a016(3), 428\u2013455 (1994)","journal-title":"Transactions on Programming Languages and Systems (TOPLAS)"},{"key":"21_CR6","volume-title":"14th International Workshop on Logic and Synthesis","author":"P. Brisk","year":"2005","unstructured":"Brisk, P., Dabiri, F., Macbeth, J., Sarrafzadeh, M.: Polynomial-time graph coloring register allocation. In: 14th International Workshop on Logic and Synthesis. ACM Press, New York (2005)"},{"key":"21_CR7","first-page":"25","volume-title":"International Conference on Programming Languages Design and Implementation","author":"Z. Budimlic","year":"2002","unstructured":"Budimlic, Z., Cooper, K.D., Harvey, T.J., Kennedy, K., Oberg, T.S., Reeves, S.W.: Fast copy coalescing and live-range identification. In: International Conference on Programming Languages Design and Implementation, pp. 25\u201332. ACM Press, New York (2002)"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Chaitin, G.J.: Register allocation and spilling via graph coloring. In: Symposium on Compiler Construction, vol.\u00a017(6), pp. 98\u2013105 (1982)","DOI":"10.1145\/800230.806984"},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s00493-005-0012-8","volume":"25","author":"M. Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Cornuejols, G., Liu, X., Seymour, P., Vuskovic, K.: Recognizing berge graphs. Combinatorica\u00a025, 143\u2013186 (2005)","journal-title":"Combinatorica"},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"Dirac, G.A.: On rigid circuit graphs. In: Abhandlungen aus dem Mathematischen Seminar der Universiat Hamburg, vol.\u00a025, pp. 71\u201375. University of Hamburg (1961)","DOI":"10.1007\/BF02992776"},{"issue":"2","key":"21_CR11","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SICOMP\u00a01(2), 180\u2013187 (1972)","journal-title":"SICOMP"},{"issue":"3","key":"21_CR12","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1145\/229542.229546","volume":"18","author":"L. George","year":"1996","unstructured":"George, L., Appel, A.W.: Iterated register coalescing. Transactions on Programming Languages and Systems (TOPLAS)\u00a018(3), 300\u2013324 (1996)","journal-title":"Transactions on Programming Languages and Systems (TOPLAS)"},{"issue":"2","key":"21_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Grotschel","year":"1981","unstructured":"Grotschel, M., Lovasz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica\u00a01(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"21_CR14","unstructured":"Hack, S.: Interference graphs of programs in SSA-form. Technical report, Universitat Karlsruhe (2005)"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Pereira, F.M.Q., Palsberg, J.: Register allocation after SSA elimination is NP-complete (2005) (Manuscript)","DOI":"10.1007\/11690634_6"},{"issue":"5","key":"21_CR16","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\u00a021(5), 895\u2013913 (1999)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"issue":"3","key":"21_CR17","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput.\u00a013(3), 566\u2013579 (1984)","journal-title":"SIAM J. Comput."},{"key":"21_CR18","volume-title":"Introduction to Graph Theory","author":"D.B. West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, Englewood Cliffs (2001)","edition":"2"},{"key":"21_CR19","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1145\/858570.858577","volume-title":"Workshop on Interpreters, virtual machines and emulators","author":"J. Whaley","year":"2003","unstructured":"Whaley, J.: Joeq: a virtual machine and compiler infrastructure. In: Workshop on Interpreters, virtual machines and emulators, pp. 58\u201366. ACM Press, New York (2003)"},{"issue":"2","key":"21_CR20","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","Programming Languages and Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11575467_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T14:57:28Z","timestamp":1605625048000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11575467_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540297352","9783540322474"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11575467_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}