{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:37:31Z","timestamp":1775054251235,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,7,15]],"date-time":"2015-07-15T00:00:00Z","timestamp":1436918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,10]]},"DOI":"10.1007\/s00224-015-9645-1","type":"journal-article","created":{"date-parts":[[2015,7,14]],"date-time":"2015-07-14T06:14:29Z","timestamp":1436854469000},"page":"416-439","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Counting the Number of Perfect Matchings in K 5-Free Graphs"],"prefix":"10.1007","volume":"59","author":[{"given":"Simon","family":"Straub","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Thierauf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabian","family":"Wagner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,15]]},"reference":[{"key":"9645_CR1","unstructured":"Barahona, F.: Balancing signed toroidal graphs in polynomial time. Technical report, University of Chile (1983)"},{"key":"9645_CR2","doi-asserted-by":"crossref","unstructured":"Di Battista, G., Tamassia, R.: Incremental planarity testing. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 436\u2013441 (1989)","DOI":"10.1109\/SFCS.1989.63515"},{"issue":"4","key":"9645_CR3","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/s004539900017","volume":"15","author":"G Di Battista","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15(4), 302\u2013318 (1996)","journal-title":"Algorithmica"},{"key":"9645_CR4","first-page":"93","volume":"38","author":"A Cayley","year":"1847","unstructured":"Cayley, A.: Sur les d\u00e9terminants gauches. J. Pure Appl. Math. 38, 93\u201396 (1847)","journal-title":"J. Pure Appl. Math."},{"key":"9645_CR5","unstructured":"Curticapean, R.: Counting perfect matchings in graphs that exclude a single-crossing minor. arXiv: 1406.4056 (2014)"},{"issue":"2","key":"9645_CR6","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.jcss.2003.12.001","volume":"69","author":"ED Demaine","year":"2004","unstructured":"Demaine, E.D., Hajiaghayi, M., Nishimura, N., Ragde, P., Thilikos, D.M.: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. Syst. Sci. 69(2), 166\u2013195 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"9645_CR7","unstructured":"Datta, S., Nimbhorkar, P., Thierauf, T., Wagner, F.: Isomorphism for K 3,3-free and K 5-free graphs is in log-space. In: Proceedings of the 29th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 145\u2013156 (2009)"},{"key":"9645_CR8","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"9645_CR9","doi-asserted-by":"crossref","unstructured":"Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of Bodlaender and Courcelle. In: 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 143\u2013152 (2010)","DOI":"10.1109\/FOCS.2010.21"},{"issue":"3","key":"9645_CR10","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0166-218X(92)00034-J","volume":"51","author":"G Galbiati","year":"1994","unstructured":"Galbiati, G., Maffioli, F.: On the computation of pfaffians. Discrete Appl. Math. 51(3), 269\u2013275 (1994)","journal-title":"Discrete Appl. Math."},{"key":"9645_CR11","volume-title":"Efficient Parallel Algorithms","author":"A Gibbons","year":"1988","unstructured":"Gibbons, A., Rytter, W.: Efficient Parallel Algorithms. Cambridge University Press, Cambridge (1988)"},{"key":"9645_CR12","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)"},{"issue":"3","key":"9645_CR13","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0022-0000(73)80013-3","volume":"7","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: A V log V $V\\log V$ algorithm for isomorphism of triconnected planar graphs. J. Comput. Syst. Sci. 7 (3), 323\u2013331 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"9645_CR14","unstructured":"Kasteleyn, P.W.: Graph theory and crystal physics. In: Harary, F. (ed.) Graph Theory and Theoretical Physics, pp 43\u2013110. Academic, New York (1967)"},{"issue":"4","key":"9645_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/cjtcs.2008.004","volume":"2008","author":"R Kulkarni","year":"2008","unstructured":"Kulkarni, R., Mahajan, M., Varadarajan, K.: Some perfect matchings and perfect half-integral matchings in NC. Chic. J. Theor. Comput. Sci. 2008(4), 1\u201326 (2008)","journal-title":"Chic. J. Theor. Comput. Sci."},{"key":"9645_CR16","doi-asserted-by":"crossref","first-page":"271","DOI":"10.4064\/fm-15-1-271-283","volume":"15","author":"K Kuratowski","year":"1930","unstructured":"Kuratowski, K.: Sur le probl\u00e9me des courbes gauches en topologie. Fundam. Math. 15, 271\u2013283 (1930)","journal-title":"Fundam. Math."},{"key":"9645_CR17","doi-asserted-by":"crossref","unstructured":"Little, C.H.C.: An extension of Kasteleyn\u2019s method of enumerating the 1-factors of planar graphs. In: Holton, D.A. (ed.) Combinatorial Mathematics, volume 403 of Lecture Notes in Mathematics, pp 63\u201372. Springer, Berlin Heidelberg (1974)","DOI":"10.1007\/BFb0057377"},{"key":"9645_CR18","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01191205","volume":"12","author":"GL Miller","year":"1992","unstructured":"Miller, G.L., Ramachandran, V.: A new graph triconnectivity algorithm and its parallelization. Combinatorica 12, 53\u201376 (1992)","journal-title":"Combinatorica"},{"issue":"1\u20133","key":"9645_CR19","doi-asserted-by":"crossref","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 Appl. Math. 143(1\u20133), 1\u201316 (2004)","journal-title":"Discrete Appl. Math."},{"key":"9645_CR20","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.: Excluding a graph with one crossing. In: Graph Structure Theory, pp. 669\u2013675. American Mathematical Society (1993)","DOI":"10.1090\/conm\/147\/01206"},{"key":"9645_CR21","doi-asserted-by":"crossref","DOI":"10.3138\/9781487584863","volume-title":"Connectivity in Graphs","author":"WT Tutte","year":"1966","unstructured":"Tutte, W.T.: Connectivity in Graphs. University of Toronto Press, Toronto (1966)"},{"key":"9645_CR22","doi-asserted-by":"crossref","unstructured":"Thierauf, T., Wagner, F.: Reachability in K 3,3-free graphs and K 5-free graphs is in unambiguous log-space. Chic. J. Theor. Comput. Sci., To appear (2014)","DOI":"10.4086\/cjtcs.2014.002"},{"key":"9645_CR23","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L Valiant","year":"1979","unstructured":"Valiant, L.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"9645_CR24","doi-asserted-by":"crossref","first-page":"1565","DOI":"10.1137\/070682575","volume":"37","author":"L Valiant","year":"2008","unstructured":"Valiant, L.: Holographic algorithms. SIAM J. Comput. 37(5), 1565\u20131594 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9645_CR25","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/0890-5401(89)90017-5","volume":"80","author":"V Vazirani","year":"1989","unstructured":"Vazirani, V.: NC algorithms for computing the number of perfect matchings in K 3,3-free graphs and related problems. Inf. Comput. 80(2), 152\u2013164 (1989)","journal-title":"Inf. Comput."},{"key":"9645_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity","author":"H Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity. Springer, Berlin (1999)"},{"issue":"1","key":"9645_CR27","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1007\/BF01594196","volume":"114","author":"K Wagner","year":"1937","unstructured":"Wagner, K.: \u00dcber eine Eigenschaft der ebenen Komplexe. Math. Ann. 114 (1), 570\u2013590 (1937)","journal-title":"Math. Ann."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9645-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9645-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9645-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,5]],"date-time":"2020-09-05T00:13:04Z","timestamp":1599264784000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9645-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,15]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,10]]}},"alternative-id":["9645"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9645-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,15]]}}}