{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T12:31:24Z","timestamp":1725798684566},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662444641"},{"type":"electronic","value":"9783662444658"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44465-8_29","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:33:02Z","timestamp":1407839582000},"page":"336-347","source":"Crossref","is-referenced-by-count":1,"title":["Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth"],"prefix":"10.1007","author":[{"given":"Kristoffer Arnsfelt","family":"Hansen","sequence":"first","affiliation":[]},{"given":"Balagopal","family":"Komarath","sequence":"additional","affiliation":[]},{"given":"Jayalal","family":"Sarma","sequence":"additional","affiliation":[]},{"given":"Sven","family":"Skyum","sequence":"additional","affiliation":[]},{"given":"Navid","family":"Talebanfard","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"29_CR1","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1006\/inco.1994.1057","volume":"112","author":"E. Allender","year":"1994","unstructured":"Allender, E., Hertrampf, U.: Depth reduction for circuits of unbounded fan-in. Information and Computation\u00a0112(2), 217\u2013238 (1994)","journal-title":"Information and Computation"},{"issue":"1","key":"29_CR2","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A.M. Barrington","year":"1989","unstructured":"Barrington, D.A.M.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. Syst. Sci.\u00a038(1), 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"29_CR3","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D.A.M. Barrington","year":"1988","unstructured":"Barrington, D.A.M., Th\u00e9rien, D.: Finite monoids and the fine structure of NC1. J. ACM\u00a035(4), 941\u2013952 (1988)","journal-title":"J. ACM"},{"key":"29_CR4","first-page":"116","volume":"36","author":"H.L. Bodlaender","year":"1988","unstructured":"Bodlaender, H.L.: Some classes of planar graphs with bounded treewidth. Bulletin of the EATCS\u00a036, 116\u2013126 (1988)","journal-title":"Bulletin of the EATCS"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M.: The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable. In: FOCS, pp. 197\u2013206. IEEE Computer Society (2013)","DOI":"10.1109\/FOCS.2013.29"},{"key":"29_CR6","unstructured":"Datta, S., Gopalan, A., Kulkarni, R., Tewari, R.: Improved bounds for bipartite matching on surfaces. In: STACS. LIPIcs, vol.\u00a014, pp. 254\u2013265. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)"},{"key":"29_CR7","unstructured":"Elberfeld, M., Jakoby, A., Tantau, T.: Algorithmic meta theorems for circuit classes of constant and logarithmic depth. In: STACS. LIPIcs, vol.\u00a014, pp. 66\u201377. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)"},{"issue":"3","key":"29_CR8","doi-asserted-by":"crossref","first-page":"775","DOI":"10.2140\/pjm.1963.13.775","volume":"13","author":"W. Feit","year":"1963","unstructured":"Feit, W., Thompson, J.G.: Solvability of groups of odd order. Pacific J. Math.\u00a013(3), 775\u20131029 (1963)","journal-title":"Pacific J. Math."},{"key":"29_CR9","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J.E., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci.\u00a010, 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"29_CR10","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci.\u00a01(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"29_CR11","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar hamiltonian circuit problem is NP-complete. SIAM J. Comput.\u00a05(4), 704\u2013714 (1976)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"29_CR12","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A. Itai","year":"1982","unstructured":"Itai, A., Papadimitriou, C.H., Szwarcfiter, J.L.: Hamilton paths in grid graphs. SIAM J. Comput.\u00a011(4), 676\u2013686 (1982)","journal-title":"SIAM J. Comput."},{"key":"29_CR13","unstructured":"Kasteleyn, P.W.: Graph theory and crystal physics. In: Harary, F. (ed.) Graph Theory and Theoretical Physics, pp. 43\u2013110. Academic Press (1967)"},{"issue":"4","key":"29_CR14","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF01137685","volume":"41","author":"A.A. Razborov","year":"1987","unstructured":"Razborov, A.A.: Lower bounds for the size of circuits of bounded depth with basis (\u2227, \u2295). Mathematical Notes of the Academy of Science of the USSR\u00a041(4), 333\u2013338 (1987)","journal-title":"Mathematical Notes of the Academy of Science of the USSR"},{"key":"29_CR15","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4) (2008)","DOI":"10.1145\/1391289.1391291"},{"issue":"1","key":"29_CR16","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. the disjoint paths problem. J. Comb. Theory, Ser. B\u00a063(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"4","key":"29_CR17","doi-asserted-by":"crossref","first-page":"780","DOI":"10.1137\/S0097539792224061","volume":"23","author":"A. Schrijver","year":"1994","unstructured":"Schrijver, A.: Finding k disjoint paths in a directed planar graph. SIAM J. Comput.\u00a023(4), 780\u2013788 (1994)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"29_CR18","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/0890-5401(89)90017-5","volume":"80","author":"V.V. Vazirani","year":"1989","unstructured":"Vazirani, V.V.: NC algorithms for computing the number of perfect matchings in K\n                  3,3-free graphs and related problems. Inf. Comput.\u00a080(2), 152\u2013164 (1989)","journal-title":"Inf. Comput."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44465-8_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T15:33:54Z","timestamp":1558971234000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44465-8_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662444641","9783662444658"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44465-8_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}