{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T17:39:57Z","timestamp":1742924397928,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540637578"},{"type":"electronic","value":"9783540696438"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0024507","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T02:30:56Z","timestamp":1132367456000},"page":"318-332","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Structured programs have small tree-width and good register allocation"],"prefix":"10.1007","author":[{"given":"Mikkel","family":"Thorup","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"S. Alstrup, P.W. Lauridsen, and M. Thorup, Generalized dominators for structured programs. In Proceedings of the 3rd Static Analysis Symposium, LNCS 1145, pages 42\u201351, 1996.","key":"26_CR1","DOI":"10.1007\/3-540-61739-6_32"},{"key":"26_CR2","volume-title":"Compilers: Principles, Techniques, and Tools","author":"A.V. Aho","year":"1986","unstructured":"A.V. Aho, R. Sethi, and J.D. Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, Reading, Mass., 1986."},{"key":"26_CR3","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D.G. Corneil, and A. Proskorowski, Complexity of Finding Embeddings in a k-Tree, SIAM J. Alg. Disc. Meth.8 (1987) 277\u2013284.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"26_CR4","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"S. Arnborg, J. Lagergren, and D. Sesse, Easy problems for tree-decomposable graphs, J. Algorithms12 (1991) 308\u2013340.","journal-title":"J. Algorithms"},{"key":"26_CR5","first-page":"11","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"S. Arnborg and A. Proskorowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, SIAM J. Alg. Disc. Meth.23 (1989) 11\u201324.","journal-title":"SIAM J. Alg. Disc. Meth."},{"doi-asserted-by":"crossref","unstructured":"L. Birkdal, M. Tofte, and M. Vejlstrup, From region inference to von Neyman Machines via region representation inference. in \u201cProc. POPL'96,\u201d pp. 171\u2013183, 1996.","key":"26_CR6","DOI":"10.1145\/237721.237771"},{"key":"26_CR7","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"H.L. Bodlaender, A Tourist Guide Through Treewidth, Acta Cybernetica11 (1993) 1\u201323.","journal-title":"Acta Cybernetica"},{"doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender, A Linear Time Algorithm for Finding Tree-Decompositions of Small Treewidth, in \u201cProc. 25th STOC,\u201d pp. 226\u2013234, 1993.","key":"26_CR8","DOI":"10.1145\/167088.167161"},{"key":"26_CR9","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0304-3975(93)90357-Y","volume":"110","author":"H.L. Bodlaender","year":"1993","unstructured":"H.L. Bodlaender, Complexity of Path Forming Games, Theor. Comp. Sc.110 (1993) 215\u2013245.","journal-title":"Theor. Comp. Sc."},{"issue":"2","key":"26_CR10","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1006\/jagm.1995.1009","volume":"18","author":"H.L. Bodlaender","year":"1995","unstructured":"H.L. Bodlaender, J.R. Gilbert, H. Hapsteinsson, and T. Kloks, Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree, J. Algorithms18, 2 (1995) 221\u2013237.","journal-title":"J. Algorithms"},{"key":"26_CR11","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R.B. Boris","year":"1992","unstructured":"R.B. Boris, R.C. Parker, and C.A. Tovey, Automatic Generation of Linear-Time Algorithms from Predicate Calculus Descriptions of Problems on Recursively Constructed Graph Families, Algorithmica7 (1992) 555\u2013581.","journal-title":"Algorithmica"},{"unstructured":"P. Briggs, Register allocation via graph coloring, PhD Thesis, Rice University, 1992.","key":"26_CR12"},{"doi-asserted-by":"crossref","unstructured":"P. Briggs, K.D. Cooper, K. Kennedy, and L. Torozon, Coloring heuristics for register allocation, in \u201cProc. SIGPLAN'89 Conf. Programming Language Design and Implementation,\u201d pp. 275\u2013284, 1989.","key":"26_CR13","DOI":"10.1145\/74818.74843"},{"doi-asserted-by":"crossref","unstructured":"D. Callahan and B. Koblenz, Register allocation via hierarchical graph coloring, in \u201cProc. SIGPLAN'91 Conf. Programming Language Design and Implementation,\u201d pp. 192\u2013203, 1991.","key":"26_CR14","DOI":"10.1145\/113446.113462"},{"doi-asserted-by":"crossref","unstructured":"G.J. Chaitin, Register Allocation and Spilling via Graph Coloring, in \u201cProc. SIGPLAN'82 Symp. Compiler Construction,\u201d pp. 98\u2013105, 1982.","key":"26_CR15","DOI":"10.1145\/800230.806984"},{"key":"26_CR16","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0096-0551(81)90048-5","volume":"6","author":"G.J. Chaitin","year":"1981","unstructured":"G.J. Chaitin, M.A. Auslander, A.K. Chandra, J. Cocks, M.E. Hoplins, and P.W. Markstein, Register allocation via graph coloring, Computer Languages6 (1981) 47\u201357.","journal-title":"Computer Languages"},{"key":"26_CR17","first-page":"49","volume":"6","author":"B. Courcelle","year":"1993","unstructured":"B. Courcelle and M. Mosbah, Monadic second-order evaluations on tree-decomposable graphs, 6 (1993) 49\u201382.","journal-title":"Monadic second-order evaluations on tree-decomposable graphs"},{"key":"26_CR18","volume-title":"Structured Programming","author":"O.J. Dahl","year":"1972","unstructured":"O.J. Dahl, E.W. Dijkstra, and C.A.R. Hoare, Structured Programming, Academic Press, London, 1972."},{"key":"26_CR19","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/S0304-3975(96)00177-6","volume":"172","author":"N. Dendris","year":"1997","unstructured":"N. Dendris, L. Kirousis, and D. Thilkos, Fugitive-serach gamses on graphs and related parameters, Theor. Comp. Sc.172 (1997) 233\u2013254.","journal-title":"Theor. Comp. Sc."},{"issue":"3","key":"26_CR20","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1145\/362929.362947","volume":"11","author":"E.W. Dijkstra","year":"1968","unstructured":"E.W. Dijkstra, Go To Statement Considered Harmful, Comm. ACM11, 3 (1968) 147\u2013148.","journal-title":"Comm. ACM"},{"issue":"4","key":"26_CR21","first-page":"785","volume":"142","author":"A.P. Ershov","year":"1962","unstructured":"A.P. Ershov, Reduction of the problem of memory allocation in programming to the problem of colouring the vertices of a graph, Doklady Academii Nauk SSSR142, 4 (1962) 785\u2013787. English version in Soviet Mathematics3 (1962) 163\u2013165.","journal-title":"Doklady Academii Nauk SSSR"},{"issue":"2","key":"26_CR22","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M.R. Carey","year":"1980","unstructured":"M.R. Carey, D.S. Johnson, G.L. Miller, and C.H. Papadimitriou, The Complexity of Coloring Circular Arcs and Chords, SIAM J. Alg. Discr. Meth.1, 2 (1980) 216\u2013227.","journal-title":"SIAM J. Alg. Discr. Meth."},{"issue":"2","key":"26_CR23","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"F. Gavril, Algorithms for Minimum Coloring; Maximum Clique, Minimum Covers by Cliques, and Maximum Independent Set of Chordal Graphs, SIAM J. Comp.1, 2 (1972) 180\u2013187.","journal-title":"SIAM J. Comp."},{"key":"26_CR24","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"F. Gavril, The Intersection Graph of Subtrees in Trees Are Exactly the Chordal Graphs, J. Comb. Th. Ser. B16 (1974) 47\u201356.","journal-title":"J. Comb. Th. Ser. B"},{"doi-asserted-by":"crossref","unstructured":"R. Gupta, M.L. Soffa, and T. Steele, Register allocation via clique separators, in \u201cProc. SIGPLAN'89 Conf. Programming Language Design and Implementation,\u201d pp. 264\u2013274, 1989.","key":"26_CR25","DOI":"10.1145\/74818.74842"},{"key":"26_CR26","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M. M. Halld\u00f3rsson","year":"1993","unstructured":"M. M. Halld\u00f3rsson, A Still Better Performance Guarantee for Approximate Graph Coloring, Inf. Proc. Lett.45 (1993) 19\u201323.","journal-title":"Inf. Proc. Lett."},{"unstructured":"S. Kannan and T. Proebsting, Register Allocation in Structured Programs, in \u201cProc. 6th SODA,\u201d pp. 360\u2013368, 1995.","key":"26_CR27"},{"key":"26_CR28","volume-title":"The C Programming Language","author":"B.R. Kernighan","year":"1978","unstructured":"B.R. Kernighan and D.M. Ritchie, The C Programming Language, Prentice-Hall, New Jersey, 1978."},{"issue":"4","key":"26_CR29","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/356635.356640","volume":"6","author":"D.E. Knuth","year":"1974","unstructured":"D.E. Knuth, Structured Programming with Go To Statements, ACM Computing Surveys6, 4 (1974) 261\u2013301.","journal-title":"ACM Computing Surveys"},{"key":"26_CR30","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"C. Lund and M. Yannakakis, On the Hardness of Approximating Minimization Problems, J. ACM41 (1994) 960\u2013981.","journal-title":"J. ACM"},{"issue":"1","key":"26_CR31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/366193.366201","volume":"6","author":"P. Naur","year":"1963","unstructured":"P. Naur, Revised Report on the Algorithmic Language Algol 60, Comm. ACM6, 1 (1963) 1\u201317.","journal-title":"Comm. ACM"},{"issue":"3","key":"26_CR32","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1007\/BF01939983","volume":"3","author":"P. Naur","year":"1963","unstructured":"P. Naur, Go To Statements and Good Algol Style, BIT3, 3 (1963) 204\u2013208.","journal-title":"BIT"},{"issue":"3","key":"26_CR33","first-page":"259","volume":"59","author":"T. Nishizeki","year":"1976","unstructured":"T. Nishizeki, K. Takamizawa, and N. Saito, Algorithms for detecting seriesparallel graphs and D-charts, Trans. Inst. Elect. Commun. Eng. Japan59, 3 (1976) 259\u2013260.","journal-title":"Trans. Inst. Elect. Commun. Eng. Japan"},{"doi-asserted-by":"crossref","unstructured":"C. Norris and L.L. Pollock, Register Allocation over the Program Dependence Graph, in \u201cProc. SIGPLAN'94 Conf. Programming Language Design and Implementation,\u201d pp. 266\u2013277, 1994.","key":"26_CR34","DOI":"10.1145\/773473.178427"},{"key":"26_CR35","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"N. Robertson and P.D. Seymour, Graph Minors 1: Excluding a Forest, J. Comb. Th. Ser. B35 (1983) 39\u201361.","journal-title":"J. Comb. Th. Ser. B"},{"key":"26_CR36","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"N. Robertson and P.D. Seymour, Graph Minors XIII: The Disjoint Paths Problem. J. Comb. Th. Ser. B63 (1995) 65\u2013110.","journal-title":"J. Comb. Th. Ser. B"},{"unstructured":"M. Thorup, Structured Programs have Small Tree-Width and Good Register Allocation, Latest full version: http,\/\/www.diku.dk\/\u2248mtharsap\/PAPERS\/register.ps.gz.","key":"26_CR37"},{"doi-asserted-by":"crossref","unstructured":"M. Tofte and J-P. Talpin, Implementing the call-by-value lambda-calculus using a stack of regions. in \u201cProc. POPL'94,\u201d pp. 188\u2013201., 1994.","key":"26_CR38","DOI":"10.1145\/174675.177855"},{"key":"26_CR39","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF00264291","volume":"1","author":"N. Wirth","year":"1971","unstructured":"N. Wirth, The Programming Language PASCAL, Acta Informatics1 (1971), 35\u201363.","journal-title":"Acta Informatics"},{"key":"26_CR40","volume-title":"Programming in Modula-2","author":"N. Wirth","year":"1985","unstructured":"N. Wirth, Programming in Modula-2 (3rd corr. ed.), Springer-Verlag, Berlin, New York, 1985.","edition":"3rd corr. ed."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0024507","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:25:49Z","timestamp":1578525949000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0024507"}},"subtitle":["extended abstract"],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540637578","9783540696438"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/bfb0024507","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"17 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}