{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T11:16:31Z","timestamp":1725880591923},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319539249"},{"type":"electronic","value":"9783319539256"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-53925-6_25","type":"book-chapter","created":{"date-parts":[[2017,2,20]],"date-time":"2017-02-20T01:12:36Z","timestamp":1487553156000},"page":"320-332","source":"Crossref","is-referenced-by-count":0,"title":["Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals"],"prefix":"10.1007","author":[{"given":"Toshiki","family":"Saitoh","sequence":"first","affiliation":[]},{"given":"David G.","family":"Kirkpatrick","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,2,21]]},"reference":[{"key":"25_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/978-3-642-38236-9_4","volume-title":"Theory and Applications of Models of Computation","author":"T Asano","year":"2013","unstructured":"Asano, T., Elmasry, A., Katajainen, J.: Priority queues and sorting for read-only data. In: Chan, T.-H.H., Lau, L.C., Trevisan, L. (eds.) TAMC 2013. LNCS, vol. 7876, pp. 32\u201341. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-38236-9_4"},{"key":"25_CR2","unstructured":"Bhattacharya, B.K., De, M., Nandy, S.C., Roy, S.: Maximum independent set for interval graphs and trees in space efficient models. In: Canadian Conference on Computational Geometry (CCCG 2014) (2014)"},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"Borodin, A.: Time space tradeos (getting closer to the barrier?). In: International Symposium on Algorithms and Computation (ISAAC 1993), pp. 209\u2013220 (1993)","DOI":"10.1007\/3-540-57568-5_251"},{"issue":"6","key":"25_CR4","doi-asserted-by":"crossref","first-page":"1671","DOI":"10.1137\/S0097539792238431","volume":"27","author":"M Chang","year":"1998","unstructured":"Chang, M.: Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput. 27(6), 1671\u20131694 (1998)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"25_CR5","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1007\/PL00009197","volume":"20","author":"S Cheng","year":"1998","unstructured":"Cheng, S., Kaminski, M., Zaks, S.: Minimum dominating sets of intervals on lines. Algorithmica 20(3), 294\u2013308 (1998)","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"25_CR6","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0012-365X(90)90357-N","volume":"86","author":"DG Corneil","year":"1990","unstructured":"Corneil, D.G., Stewart, L.K.: Dominating sets in perfect graphs. Discrete Math. 86(1\u20133), 145\u2013164 (1990)","journal-title":"Discrete Math."},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Darwish, O., Elmasry, A.: Optimal time-space tradeo for the 2D convex-hull problem. In: European Symposium on Algorithms (ESA 2014), pp. 284\u2013295 (2014)","DOI":"10.1007\/978-3-662-44777-2_24"},{"issue":"1","key":"25_CR8","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0022-0000(87)90002-X","volume":"34","author":"GN Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Upper bounds for time-space trade-offs in sorting and selection. J. Comput. Syst. Sci. 34(1), 19\u201326 (1987)","journal-title":"J. Comput. Syst. Sci."},{"key":"25_CR9","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57. Elsevier, Amsterdam (2004)"},{"issue":"3","key":"25_CR10","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1016\/0196-6774(88)90023-5","volume":"9","author":"MC Golumbic","year":"1988","unstructured":"Golumbic, M.C., Hammer, P.L.: Stability in circular arc graphs. J. Algorithms 9(3), 314\u2013320 (1988)","journal-title":"J. Algorithms"},{"key":"25_CR11","series-title":"Chapman & Hall\/CRC Pure and Applied Mathematics","volume-title":"Fundamentals of Domination in Graphs","author":"T Haynes","year":"1998","unstructured":"Haynes, T., Hedetniemi, S., Slater, P.: Fundamentals of Domination in Graphs. Chapman & Hall\/CRC Pure and Applied Mathematics. CRC Press, Boca Raton (1998)"},{"issue":"2","key":"25_CR12","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1006\/jagm.1995.1031","volume":"19","author":"W Hsu","year":"1995","unstructured":"Hsu, W., Spinrad, J.P.: Independent sets in circular-arc graphs. J. Algorithms 19(2), 145\u2013160 (1995)","journal-title":"J. Algorithms"},{"issue":"3","key":"25_CR13","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0020-0190(91)90165-E","volume":"40","author":"W Hsu","year":"1991","unstructured":"Hsu, W., Tsai, K.: Linear time algorithms on circular-arc graphs. Inf. Process. Lett. 40(3), 123\u2013129 (1991)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"25_CR14","first-page":"238","volume":"10","author":"J Katajainen","year":"2003","unstructured":"Katajainen, J., Vitale, F.: Navigation piles with applications to sorting, priority queues, and priority deques. Nordic J. Comput. 10(3), 238\u2013262 (2003)","journal-title":"Nordic J. Comput."},{"key":"25_CR15","volume-title":"Algorithm Design","author":"J Kleinberg","year":"2005","unstructured":"Kleinberg, J., Tardos, E.: Algorithm Design. Addison-Wesley Longman Publishing Co., Inc., Boston (2005)"},{"key":"25_CR16","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"JI Munro","year":"1980","unstructured":"Munro, J.I., Paterson, M.: Selection and sorting with limited storage. Theor. Comput. Sci. 12, 315\u2013323 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"Pagter, J., Rauhe, T.: Optimal time-space trade-offs for sorting. In: Foundations of Computer Science (FOCS 1998), pp. 264\u2013268 (1998)","DOI":"10.1109\/SFCS.1998.743455"},{"issue":"2","key":"25_CR18","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1002\/net.20150","volume":"49","author":"J Snoeyink","year":"2007","unstructured":"Snoeyink, J.: Maximum independent set for intervals by divide and conquer with pruning. Networks 49(2), 158\u2013159 (2007)","journal-title":"Networks"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-53925-6_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T21:30:45Z","timestamp":1568842245000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-53925-6_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319539249","9783319539256"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-53925-6_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}