{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T19:34:41Z","timestamp":1725824081765},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319213972"},{"type":"electronic","value":"9783319213989"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21398-9_28","type":"book-chapter","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T11:12:41Z","timestamp":1435057961000},"page":"349-360","source":"Crossref","is-referenced-by-count":6,"title":["Time-Space Tradeoffs for Dynamic Programming Algorithms in Trees and Bounded Treewidth Graphs"],"prefix":"10.1007","author":[{"given":"Niranka","family":"Banerjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sankardeep","family":"Chakraborty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sasanka","family":"Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"key":"28_CR1","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. Journal of Algorithms 12, 308\u2013340 (1991)","journal-title":"Journal of Algorithms"},{"key":"28_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/978-3-642-00826-9_12","volume-title":"Emerging Trends in Visual Computing","author":"T Asano","year":"2009","unstructured":"Asano, T.: Constant-Working-Space Algorithms for Image Processing. In: Nielsen, F. (ed.) ETVC 2008. LNCS, vol. 5416, pp. 268\u2013283. Springer, Heidelberg (2009)"},{"key":"28_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-92182-0_1","volume-title":"Algorithms and Computation","author":"T Asano","year":"2008","unstructured":"Asano, T.: Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array? In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 1\u20131. Springer, Heidelberg (2008)"},{"key":"28_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-20877-5_1","volume-title":"Theory and Applications of Models of Computation","author":"T Asano","year":"2011","unstructured":"Asano, T.: Designing Algorithms with Limited Work Space. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol. 6648, pp. 1\u20131. Springer, Heidelberg (2011)"},{"key":"28_CR5","unstructured":"Asano, T., Doerr, B.: Memory-constrained algorithms for shortest path problem. In: Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, CCCG (2011)"},{"key":"28_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/978-3-662-44465-8_5","volume-title":"Mathematical Foundations of Computer Science 2014","author":"T Asano","year":"2014","unstructured":"Asano, T., Kirkpatrick, D., Nakagawa, K., Watanabe, O.: $$\\widetilde{O}(\\sqrt{n})$$ O ~ ( n ) -Space and polynomial-time algorithm for planar directed graph reachability. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 45\u201356. Springer, Heidelberg (2014)"},{"issue":"1","key":"28_CR7","first-page":"46","volume":"2","author":"T Asano","year":"2011","unstructured":"Asano, T., Mulzer, W., Rote, G., Wang, Y.: Constant-work-space algorithms for geometric problems. JoCG 2(1), 46\u201368 (2011)","journal-title":"Constant-work-space algorithms for geometric problems. JoCG"},{"issue":"5","key":"28_CR8","doi-asserted-by":"publisher","first-page":"569","DOI":"10.7155\/jgaa.00240","volume":"15","author":"T Asano","year":"2011","unstructured":"Asano, T., Mulzer, W., Wang, Y.: Constant-work-space algorithms for shortest paths in trees and simple polygons. J. Graph Algorithms Appl. 15(5), 569\u2013586 (2011)","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"28_CR9","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/s004530010025","volume":"27","author":"B Aspvall","year":"2000","unstructured":"Aspvall, B., Telle, J.A., Proskurowski, A.: Memory requirements for table computations in partial k-tree algorithms. Algorithmica 27(3), 382\u2013394 (2000)","journal-title":"Algorithmica"},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"Barba, L., Korman, M., Langerman, S., Sadakane, K., Silveira, R.: Space-time trade-offs for stack-based algorithms. Algorithmica (2014) (in press)","DOI":"10.1007\/s00453-014-9893-5"},{"key":"28_CR11","unstructured":"Bhattacharya, B.K., De, M., Nandy, S.C., Roy, S.: Maximum independent set for interval graphs and trees in space efficient models. In: Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG (2014)"},{"issue":"6","key":"28_CR12","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"28_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1\u20132), 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"28_CR14","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51(3), 255\u2013269 (2008)","journal-title":"Comput. J."},{"issue":"4","key":"28_CR15","first-page":"374","volume":"11","author":"HL Bodlaende","year":"2004","unstructured":"Bodlaende, H.L., Telle, J.A.: Space-efficient construction variants of dynamic programming. Nord. J. Comput. 11(4), 374\u2013385 (2004)","journal-title":"Nord. J. Comput."},{"issue":"5&6","key":"28_CR16","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"RB Borie","year":"1992","unstructured":"Borie, R.B.: Gary Parker, R., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7(5&6), 555\u2013581 (1992)","journal-title":"Algorithmica"},{"issue":"4","key":"28_CR17","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1142\/S0218195902000906","volume":"12","author":"P Bose","year":"2002","unstructured":"Bose, P., Morin, P.: An improved algorithm for subdivision traversal without extra storage. Int. J. Comput. Geometry Appl. 12(4), 297\u2013308 (2002)","journal-title":"Int. J. Comput. Geometry Appl."},{"key":"28_CR18","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press (2009)"},{"key":"28_CR19","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Inform. and Comput. 85, 12\u201375 (1990)","journal-title":"Inform. and Comput."},{"key":"28_CR20","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic. In: Handbook of Graph Grammars and Computing by Graph Transformation, vol. 1, pp. 313\u2013400. World Sci. Publ., River Edge (1997)","DOI":"10.1142\/9789812384720_0005"},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic. Cambridge University Press (2012)","DOI":"10.1017\/CBO9780511977619"},{"key":"28_CR22","doi-asserted-by":"crossref","unstructured":"Datta, S., Limaye, N., Nimbhorkar, P., Thierauf, T., Wagner, F.: Planar graph isomorphism is in log-space. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, pp. 203\u2013214 (2009)","DOI":"10.1109\/CCC.2009.16"},{"key":"28_CR23","unstructured":"De, M., Nandy, S.C., Roy, S.: Convex hull and linear programming in read-only setup with limited work-space. CoRR, abs\/1212.5353 (2012)"},{"key":"28_CR24","doi-asserted-by":"crossref","unstructured":"Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of bodlaender and courcelle. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, pp. 143\u2013152 (2010)","DOI":"10.1109\/FOCS.2010.21"},{"issue":"1","key":"28_CR25","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1137\/120892234","volume":"44","author":"M Grohe","year":"2015","unstructured":"Grohe, M., Marx, D.: Structure theorem and isomorphism test for graphs with excluded topological subgraphs. SIAM J. Comput. 44(1), 114\u2013159 (2015)","journal-title":"SIAM J. Comput."},{"key":"28_CR26","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"28_CR27","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 17:1\u201317:24 (2008)","DOI":"10.1145\/1391289.1391291"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21398-9_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T14:33:19Z","timestamp":1691764399000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-21398-9_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319213972","9783319213989"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21398-9_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}