{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:50:38Z","timestamp":1759063838411},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540771180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77120-3_13","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T11:31:09Z","timestamp":1196940669000},"page":"124-136","source":"Crossref","is-referenced-by-count":9,"title":["On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices"],"prefix":"10.1007","author":[{"given":"Uffe","family":"Flarup","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Koiran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurent","family":"Lyaudet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1287\/moor.21.1.65","volume":"21","author":"A. Barvinok","year":"1996","unstructured":"Barvinok, A.: Two algorithmic results for the traveling salesman problem. Mathematics of Operations Research\u00a021, 65\u201384 (1996)","journal-title":"Mathematics of Operations Research"},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H.L. Bodlaender","year":"1989","unstructured":"Bodlaender, H.L.: NC-algorithms for graphs with small treewidth. In: van Leeuwen, J. (ed.) Graph-Theoretic Concepts in Computer Science. LNCS, vol.\u00a0344, pp. 1\u201310. Springer, Heidelberg (1989)"},{"key":"13_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1007\/3-540-60084-1_80","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Hagerup, T.: Parallel Algorithms with Optimal Speedup for Bounded Treewidth. In: F\u00fcl\u00f6p, Z., Gecseg, F. (eds.) Automata, Languages and Programming. LNCS, vol.\u00a0944, pp. 268\u2013279. Springer, Heidelberg (1995)"},{"key":"13_CR4","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04179-6","volume-title":"Completeness and Reduction in Algebraic Complexity Theory","author":"P. B\u00fcrgisser","year":"2000","unstructured":"B\u00fcrgisser, P.: Completeness and Reduction in Algebraic Complexity Theory. Algorithms and Computation in Mathematics, vol.\u00a07. Springer, Heidelberg (2000)"},{"key":"13_CR5","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1090\/conm\/147\/01200","volume":"147","author":"B. Courcelle","year":"1993","unstructured":"Courcelle, B.: Graph Grammars, Monadic Second-Order Logic And The Theory Of Graph Minors. Contemporary Mathematics\u00a0147, 565\u2013590 (1993)","journal-title":"Contemporary Mathematics"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"B. Courcelle","year":"2001","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics\u00a0108, 23\u201352 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"13_CR7","first-page":"43","volume-title":"Graph Theory and Theoretical Physics","author":"P.W. Kasteleyn","year":"1967","unstructured":"Kasteleyn, P.W.: Graph theory and crystal physics. In: Harary, F. (ed.) Graph Theory and Theoretical Physics, pp. 43\u2013110. Academic Press, London (1967)"},{"key":"13_CR8","unstructured":"Mackworth, A.K., Zhang, Y.: Parallel and Distributed Finite Constraint Satisfaction. Technical Report 92-30, Department of Computer Science, University of British Columbia, Vancouver, B. C. Canada (1992)"},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2003.12.001","volume":"143","author":"M. Mahajan","year":"2004","unstructured":"Mahajan, M., Subramanya, P.R., Vinay, V.: The combinatorial approach yields an NC algorithm for computing Pfaffians. Discrete Applied Mathematics\u00a0143, 1\u201316 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"13_CR10","first-page":"211","volume-title":"Proceedings of the Smalefest 2000","author":"J.A. Makowsky","year":"2002","unstructured":"Makowsky, J.A., Meer, K.: Polynomials of bounded treewidth. Foundations of Computational Mathematics. In: Cucker, F., Maurice Rojas, J. (eds.) Proceedings of the Smalefest 2000, pp. 211\u2013250. World Scientific, Singapore (2002)"},{"key":"13_CR11","unstructured":"Malod, G.: Polyn\u00f4mes et coefficients. Ph.D. thesis (2003)"},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1007\/11821069_61","volume-title":"Mathematical Foundations of Computer Science 2006","author":"G. Malod","year":"2006","unstructured":"Malod, G., Portier, N.: Characterizing Valiant\u2019s Algebraic Complexity Classes. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 704\u2013716. Springer, Heidelberg (2006)"},{"key":"13_CR13","first-page":"116","volume":"E75-D","author":"S. Toda","year":"1992","unstructured":"Toda, S.: Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Transactions on Information and Systems\u00a0E75-D, 116\u2013124 (1992)","journal-title":"IEICE Transactions on Information and Systems"},{"key":"13_CR14","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science\u00a08, 181\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: Proc. 11th ACM Symposium on Theory of Computing, pp. 249\u2013261 (1979)","DOI":"10.1145\/800135.804419"},{"key":"13_CR16","unstructured":"Valiant, L.G.: Reducibility by algebraic projections. In: Logic and Algorithmic (an International Symposium held in honour of Ernst Specker), pp. 365\u2013380. Monographie n\u00b0 30 de L\u2019Enseignement Math\u00e9matique (1982)"},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1109\/FOCS.2004.34","volume-title":"Proc. 45th Annual IEEE Symposium on Foundations of Computer Science","author":"L.G. Valiant","year":"2004","unstructured":"Valiant, L.G.: Holographic algorithms. In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 306\u2013315. IEEE Press, Los Alamitos (2004)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77120-3_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:01:02Z","timestamp":1619521262000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77120-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540771180"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77120-3_13","relation":{},"subject":[]}}