{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:58:18Z","timestamp":1725861498883},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319426334"},{"type":"electronic","value":"9783319426341"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-42634-1_8","type":"book-chapter","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T11:50:21Z","timestamp":1468929021000},"page":"92-102","source":"Crossref","is-referenced-by-count":2,"title":["The Monotone Circuit Value Problem with Bounded Genus Is in NC"],"prefix":"10.1007","author":[{"given":"Faisal N.","family":"Abu-Khzam","sequence":"first","affiliation":[]},{"given":"Shouwei","family":"Li","sequence":"additional","affiliation":[]},{"given":"Christine","family":"Markarian","sequence":"additional","affiliation":[]},{"given":"Friedhelm","family":"Meyer auf der Heide","sequence":"additional","affiliation":[]},{"given":"Pavel","family":"Podlipyan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"issue":"6","key":"8_CR1","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1090\/S0002-9904-1962-10847-7","volume":"68","author":"J Battle","year":"1962","unstructured":"Battle, J., Harary, F., Kodama, Y.: Additivity of the genus of a graph. Bull. Am. Math. Soc. 68(6), 565\u2013568 (1962)","journal-title":"Bull. Am. Math. Soc."},{"issue":"3","key":"8_CR2","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1007\/BFb0057945","volume-title":"Euro-Par\u201998 Parallel Processing","author":"M Cesati","year":"1998","unstructured":"Cesati, M., Di Ianni, M.: Parameterized parallel complexity. In: Pritchard, D., Reeve, J.S. (eds.) Euro-Par 1998. LNCS, vol. 1470, pp. 892\u2013896. Springer, Heidelberg (1998)"},{"issue":"40","key":"8_CR4","doi-asserted-by":"crossref","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"8_CR5","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"SA Cook","year":"1985","unstructured":"Cook, S.A.: A taxonomy of problems with fast parallel algorithms. Inf. Control 64(1), 2\u201322 (1985)","journal-title":"Inf. Control"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of bodlaender and courcelle. In: 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 143\u2013152. IEEE (2010)","DOI":"10.1109\/FOCS.2010.21"},{"issue":"2","key":"8_CR7","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1008354.1008356","volume":"9","author":"LM Goldschlager","year":"1977","unstructured":"Goldschlager, L.M.: The monotone and planar circuit value problems are log space complete for P. SIGACT News 9(2), 25\u201329 (1977)","journal-title":"SIGACT News"},{"issue":"2","key":"8_CR8","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/0022-0000(88)90006-2","volume":"37","author":"PN Klein","year":"1988","unstructured":"Klein, P.N., Reif, J.H.: An efficient parallel algorithm for planarity. J. Comput. Syst. Sci. 37(2), 190\u2013246 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"8_CR9","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"RE Ladner","year":"1975","unstructured":"Ladner, R.E.: The circuit value problem is log space complete for P. SIGACT News 7(1), 18\u201320 (1975)","journal-title":"SIGACT News"},{"issue":"3","key":"8_CR10","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/s00037-009-0265-5","volume":"18","author":"N Limaye","year":"2009","unstructured":"Limaye, N., Mahajan, M., Sarma, J.M.: Upper bounds for monotone planar circuit value and variants. Comput. Complex. 18(3), 377\u2013412 (2009)","journal-title":"Comput. Complex."},{"issue":"2","key":"8_CR11","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1137\/S0097539793260775","volume":"25","author":"V Ramachandran","year":"1996","unstructured":"Ramachandran, V., Yang, H.: An efficient parallel algorithm for the general planar monotone circuit value problem. SIAM J. Comput. 25(2), 312\u2013339 (1996)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"8_CR12","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E., Vishkin, U.: An efficient parallel biconnectivity algorithm. SIAM J. Comput. 14(4), 862\u2013874 (1985)","journal-title":"SIAM J. Comput."},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Yang, H.: An NC algorithm for the general planar monotone circuit value problem. In: Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing, pp. 196\u2013203, December 1991","DOI":"10.1109\/SPDP.1991.218279"}],"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-42634-1_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T14:44:10Z","timestamp":1498315450000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-42634-1_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319426334","9783319426341"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-42634-1_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}