{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:21:31Z","timestamp":1725571291191},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175138"},{"type":"electronic","value":"9783642175145"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17514-5_19","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T15:09:23Z","timestamp":1291388963000},"page":"218-229","source":"Crossref","is-referenced-by-count":0,"title":["Single and Multiple Device DSA Problem, Complexities and Online Algorithms"],"prefix":"10.1007","author":[{"given":"Weiwei","family":"Wu","sequence":"first","affiliation":[]},{"given":"Wanyong","family":"Tian","sequence":"additional","affiliation":[]},{"given":"Minming","family":"Li","sequence":"additional","affiliation":[]},{"given":"Chun Jason","family":"Xue","sequence":"additional","affiliation":[]},{"given":"Enhong","family":"Chen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"19_CR1","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. ACM Transactions on Programming Languages and Systems\u00a016(3), 428\u2013455 (1994)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Buchsbaum, A.L., Karloff, H., Kenyon, C., Reingold, N., Thorup, M.: OPT versus LOAD in dynamic storage allocation. In: Proceedioings of the 35th Annual ACM Symposium on Therory of Computing (STOC), pp. 556\u2013564 (2003)","DOI":"10.1145\/780542.780624"},{"key":"19_CR3","unstructured":"Buchsbaum, A.L., Efrat, A., Jain, S., Venkatasubramanian, S.: Restricted strip covering and the sensor cover problem. The Conference version appears in Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1056\u20131063 (2007), The full version is at http:\/\/arxiv.org\/PS_cache\/cs\/pdf\/0605\/0605102v1.pdf"},{"key":"19_CR4","first-page":"98","volume-title":"Proceedings of the SIGPLAN Symposium on Compiler Construction","author":"G.J. Chaitin","year":"1982","unstructured":"Chaitin, G.J.: Register allocation & spilling via graph coloring. In: Proceedings of the SIGPLAN Symposium on Compiler Construction, pp. 98\u2013105. ACM Press, New York (1982)"},{"issue":"4","key":"19_CR5","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/88616.88621","volume":"12","author":"F.C. Chow","year":"1990","unstructured":"Chow, F.C., Hennessy, J.L.: The priority-based coloring approach to register allocation. ACM Transactions on Programming Languages and Systems\u00a012(4), 501\u2013536 (1990)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"issue":"3","key":"19_CR6","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. ACM Transactions on Programming Languages and Systems\u00a018(3), 300\u2013324 (1996)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-61680-2_46","volume-title":"Algorithms - ESA \u201996","author":"J. Gergov","year":"1996","unstructured":"Gergov, J.: Approximation algorithms for dynamic storage allocation. In: D\u00edaz, J. (ed.) ESA 1996. LNCS, vol.\u00a01136, pp. 52\u201361. Springer, Heidelberg (1996)"},{"key":"19_CR8","unstructured":"Gergov, J.: Algorithms for compile-time memory optimization. In: Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. S907\u2013S908 (1999)"},{"key":"19_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/3-540-44450-5_34","volume-title":"FST TCS 2000: Foundations of Software Technology and Theoretical Science","author":"B. Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.R.: Dynamic Spectrum Allocation: The Impotency of Duration Notification. In: Kapoor, S., Prasad, S. (eds.) FST TCS 2000. LNCS, vol.\u00a01974, pp. 421\u2013428. Springer, Heidelberg (2000)"},{"issue":"4","key":"19_CR10","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1137\/0401048","volume":"1","author":"H.A. Kierstead","year":"1988","unstructured":"Kierstead, H.A.: The linearity of first-fit colorings of interval graphs. SIAM Journal on Discrete Mathematics\u00a01(4), 526\u2013530 (1988)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"19_CR11","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0012-365X(91)90011-P","volume":"88","author":"H.A. Kierstead","year":"1991","unstructured":"Kierstead, H.A.: A polynomial time approximation algorithm for dynamic storage allocation. Discrete Mathematics\u00a088, 231\u2013237 (1991)","journal-title":"Discrete Mathematics"},{"key":"19_CR12","volume-title":"Foundamental algorithms","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: Foundamental algorithms, 2nd edn., vol.\u00a01. Addison-Wesley, Reading (1973)","edition":"2"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Li, S.C., Leong, H.W., Quek, S.K.: New approximation algorithms for some dynamic storage allocation problems. In: Proceedings of the 10th Annual International Computing and Combinatorics Conference, pp. 339\u2013348 (2004)","DOI":"10.1007\/978-3-540-27798-9_37"},{"key":"19_CR14","unstructured":"Luby, M.G., Naor, J., Orda, A.: Tight bounds for dynamic storage allocation. In: Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 724\u2013732 (1994)"},{"key":"#cr-split#-19_CR15.1","doi-asserted-by":"crossref","unstructured":"Naor, J., Orda, A., Petruschka, Y.: Dynamic storage allocation with known durations. In: Proceedings of the 5th Annual European Symposium on Algorithms (ESA), pp. 378???387 (1997);","DOI":"10.1007\/3-540-63397-9_29"},{"key":"#cr-split#-19_CR15.2","doi-asserted-by":"crossref","unstructured":"The journal version appreas in Discrete Applied Mathematics 100(3), 203???213 (2000)","DOI":"10.1016\/S0166-218X(99)00175-4"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Narayanaswamy, N.S.: Dynamic storage allocation and on-line colouring interval graphs. In: Proceedings of the 10th Annual International Computing and Combinatorics Conference, pp. 329\u2013338 (2004)","DOI":"10.1007\/978-3-540-27798-9_36"},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1093\/comjnl\/20.3.242","volume":"20","author":"J.M. Robson","year":"1977","unstructured":"Robson, J.M.: Worst case fragmentation of first-fit and best fit storage allocation strategies. Computer Journal\u00a020, 242\u2013244 (1977)","journal-title":"Computer Journal"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"Yang, X., Wang, L., Xue, J., Deng, Y., Zhang, Y.: Comparability graph coloring for optimizing utilization of stream register files in stream processors. In: Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 111\u2013120 (2009)","DOI":"10.1145\/1594835.1504195"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17514-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T15:49:11Z","timestamp":1559836151000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17514-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175138","9783642175145"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17514-5_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}