{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T19:35:01Z","timestamp":1725824101223},"publisher-location":"Cham","reference-count":13,"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_7","type":"book-chapter","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T15:12:41Z","timestamp":1435072361000},"page":"83-94","source":"Crossref","is-referenced-by-count":4,"title":["Reversible Pebble Game on Trees"],"prefix":"10.1007","author":[{"given":"Balagopal","family":"Komarath","sequence":"first","affiliation":[]},{"given":"Jayalal","family":"Sarma","sequence":"additional","affiliation":[]},{"given":"Saurabh","family":"Sawlani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"issue":"4","key":"7_CR1","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1137\/0218053","volume":"18","author":"CH Bennett","year":"1989","unstructured":"Bennett, C.H.: Time\/space trade-offs for reversible computation. SIAM Journal of Computing 18(4), 766\u2013776 (1989)","journal-title":"SIAM Journal of Computing"},{"doi-asserted-by":"crossref","unstructured":"Chan, S.M.: Just a pebble game. In: Proceedings of the 28th Conference on Computational Complexity (CCC), pp. 133\u2013143 (2013)","key":"7_CR2","DOI":"10.1109\/CCC.2013.22"},{"doi-asserted-by":"crossref","unstructured":"Chan, S.M.: Pebble Games and Complexity. PhD thesis, EECS Department, University of California, Berkeley, August 2013","key":"7_CR3","DOI":"10.1109\/CCC.2013.22"},{"issue":"2","key":"7_CR4","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0022-0000(85)90011-X","volume":"30","author":"PW Dymond","year":"1985","unstructured":"Dymond, P.W., Tompa, M.: Speedups of deterministic machines by synchronous parallel machines. Journal of Computer and System Sciences 30(2), 149\u2013161 (1985)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"7_CR5","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/0209038","volume":"9","author":"JR Gilbert","year":"1980","unstructured":"Gilbert, J.R., Lengauer, T., Tarjan, R.E.: The pebbling problem is complete in polynomial space. SIAM Journal on Computing 9(3), 513\u2013524 (1980)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"7_CR6","doi-asserted-by":"publisher","first-page":"2622","DOI":"10.1137\/080713513","volume":"39","author":"P Hertel","year":"2010","unstructured":"Hertel, P., Pitassi, T.: The pspace-completeness of black-white pebbling. SIAM J. Comput. 39(6), 2622\u20132682 (2010)","journal-title":"SIAM J. Comput."},{"key":"7_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/3-540-45627-9_26","volume-title":"SOFSEM 2001: Theory and Practice of Informatics","author":"R Kr\u00e1l\u2019ovic","year":"2001","unstructured":"Kr\u00e1l\u2019ovic, R.: Time and space complexity of reversible pebbling. In: Pacholski, L., Ru\u017ei\u010dka, P. (eds.) SOFSEM 2001. LNCS, vol. 2234, p. 292. Springer, Heidelberg (2001)"},{"unstructured":"Lam, T.W., Yue, F.L.: Optimal edge ranking of trees in linear time. In: Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 436\u2013445 (1998)","key":"7_CR8"},{"unstructured":"Loui, M.C.: The space complexity of two pebbles games on trees. Technical Report MIT\/LCS\/TM-133, Massachusetts Institute of Technology (1979)","key":"7_CR9"},{"issue":"3","key":"7_CR10","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s004930050062","volume":"19","author":"R Raz","year":"1999","unstructured":"Raz, R., McKenzie, P.: Separation of the monotone NC hierarchy. Combinatorica 19(3), 403\u2013435 (1999). Conference version appeared in proceedings of 38th Annual Symposium on Foundations of Computer Science (FOCS 1997, Pages 234\u2013243)","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"Sethi, R.: Complete register allocation problems. SIAM Journal on Computing, pp. 226\u2013248(1975)","key":"7_CR11","DOI":"10.1137\/0204020"},{"unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, September 2000","key":"7_CR12"},{"issue":"4","key":"7_CR13","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1145\/4221.4228","volume":"32","author":"M Yannakakis","year":"1985","unstructured":"Yannakakis, M.: A polynomial algorithm for the min-cut linear arrangement of trees. Journal of the ACM 32(4), 950\u2013988 (1985)","journal-title":"Journal of the ACM"}],"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_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T08:25:59Z","timestamp":1559204759000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-21398-9_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319213972","9783319213989"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21398-9_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}