{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T11:08:23Z","timestamp":1742987303294,"version":"3.40.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030738785"},{"type":"electronic","value":"9783030738792"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-73879-2_16","type":"book-chapter","created":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T23:04:59Z","timestamp":1620169499000},"page":"223-237","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems"],"prefix":"10.1007","author":[{"given":"Kazuki","family":"Matoya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taihei","family":"Oki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,5,5]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","unstructured":"Anari, N., Gharan, S.O., Vinzant, C.: Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids. In: Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018), pp. 35\u201346 (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00013","DOI":"10.1109\/FOCS.2018.00013"},{"key":"16_CR2","doi-asserted-by":"publisher","unstructured":"Anari, N., Liu, K., Gharan, S.O., Vinzant, C.: Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. In: Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC 2019), pp. 1\u201312 (2019). https:\/\/doi.org\/10.1145\/3313276.3316385","DOI":"10.1145\/3313276.3316385"},{"issue":"3","key":"16_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2601066","volume":"10","author":"HY Cheung","year":"2014","unstructured":"Cheung, H.Y., Lau, L.C., Leung, K.M.: Algebraic algorithms for linear matroid parity problems. ACM Trans. Algorithms 10(3), 1\u201326 (2014). https:\/\/doi.org\/10.1145\/2601066","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"16_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01294456","volume":"15","author":"CJ Colbourn","year":"1995","unstructured":"Colbourn, C.J., Provan, J.S., Vertigan, D.: The complexity of computing the Tutte polynomial on transversal matroids. Combinatorica 15(1), 1\u201310 (1995). https:\/\/doi.org\/10.1007\/BF01294456","journal-title":"Combinatorica"},{"key":"16_CR5","doi-asserted-by":"publisher","unstructured":"Edmonds, J.: Matroid partition. In: Dantzig, G.B., Veinott, Jr., A.F. (eds.) Mathematics of the Decision Sciences: Part I, Lectures in Applied Mathematics, vol. 11, pp. 335\u2013345. AMS, Providence, RI (1968). https:\/\/doi.org\/10.1007\/978-3-540-68279-0_7","DOI":"10.1007\/978-3-540-68279-0_7"},{"key":"16_CR6","doi-asserted-by":"publisher","unstructured":"Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Guy, R., Hanani, H., Sauer, N., Sch\u00f6nheim, J. (eds.) Combinatorial Structures and Their Applications, pp. 69\u201387. Gordon and Breach, New York, NY (1970). https:\/\/doi.org\/10.1007\/3-540-36478-1_2","DOI":"10.1007\/3-540-36478-1_2"},{"key":"16_CR7","unstructured":"Frank, A.: Connections in Combinatorial Optimization. Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, New York, NY (2011)"},{"issue":"2","key":"16_CR8","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF02579169","volume":"6","author":"HN Gabow","year":"1986","unstructured":"Gabow, H.N., Stallmann, M.: An augmenting path algorithm for linear matroid parity. Combinatorica 6(2), 123\u2013150 (1986). https:\/\/doi.org\/10.1007\/BF02579169","journal-title":"Combinatorica"},{"issue":"1","key":"16_CR9","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1006\/jcss.1996.0054","volume":"53","author":"HN Gabow","year":"1996","unstructured":"Gabow, H.N., Xu, Y.: Efficient theoretic and practical algorithms for linear matroid intersection problems. J. Comput. Syst. Sci. 53(1), 129\u2013147 (1996). https:\/\/doi.org\/10.1006\/jcss.1996.0054","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR10","doi-asserted-by":"publisher","unstructured":"Gallai, T.: Maximum-Minimum S\u00e4tze und verallgemeinerte Faktoren von Graphen. Acta Mathematica Academiae Scientiarum Hungaricae 12, 131\u2013173 (1964). https:\/\/doi.org\/10.1007\/BF02066678","DOI":"10.1007\/BF02066678"},{"issue":"3","key":"16_CR11","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0001-8708(85)90121-5","volume":"58","author":"I Gessel","year":"1985","unstructured":"Gessel, I., Viennot, G.: Binomial determinants, paths, and hook length formulae. Adv. Math. 58(3), 300\u2013321 (1985). https:\/\/doi.org\/10.1016\/0001-8708(85)90121-5","journal-title":"Adv. Math."},{"issue":"4","key":"16_CR12","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1016\/j.aam.2011.04.006","volume":"47","author":"A Goodall","year":"2011","unstructured":"Goodall, A., De Mier, A.: Spanning trees of 3-uniform hypergraphs. Adv. Appl. Math. 47(4), 840\u2013868 (2011). https:\/\/doi.org\/10.1016\/j.aam.2011.04.006","journal-title":"Adv. Appl. Math."},{"issue":"2","key":"16_CR13","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1137\/070684008","volume":"39","author":"NJA Harvey","year":"2009","unstructured":"Harvey, N.J.A.: Algebraic algorithms for matching and matroid problems. SIAM J. Comput. 39(2), 679\u2013702 (2009). https:\/\/doi.org\/10.1137\/070684008","journal-title":"SIAM J. Comput."},{"issue":"3","key":"16_CR14","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1080\/03081089508818403","volume":"39","author":"M Ishikawa","year":"1995","unstructured":"Ishikawa, M., Wakayama, M.: Minor summation formula of Pfaffians. Linear Multilinear Algebra 39(3), 285\u2013305 (1995). https:\/\/doi.org\/10.1080\/03081089508818403","journal-title":"Linear Multilinear Algebra"},{"key":"16_CR15","doi-asserted-by":"publisher","unstructured":"Iwata, S., Kobayashi, Y.: A weighted linear matroid parity algorithm. SIAM J. Comput. (to appear). https:\/\/doi.org\/10.1137\/17M1141709","DOI":"10.1137\/17M1141709"},{"key":"16_CR16","doi-asserted-by":"publisher","unstructured":"Kasteleyn, P.W.: The statistics of dimers on a lattice: I. the number of dimer arrangements on a quadratic lattice. Physica, 27(12), 1209\u20131225 (1961). https:\/\/doi.org\/10.1016\/0031-8914(61)90063-5","DOI":"10.1016\/0031-8914(61)90063-5"},{"key":"16_CR17","first-page":"43","volume-title":"Graph Theory and Theoretical Physics","author":"PW 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, New York, NY (1967)"},{"issue":"12","key":"16_CR18","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1002\/andp.18471481202","volume":"148","author":"G Kirchhoff","year":"1847","unstructured":"Kirchhoff, G.: Ueber die Aufl\u00f6sung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Str\u00f6me gef\u00fchrt wird. Annalen der Physik 148(12), 497\u2013508 (1847). https:\/\/doi.org\/10.1002\/andp.18471481202","journal-title":"Annalen der Physik"},{"key":"16_CR19","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"EL Lawler","year":"1976","unstructured":"Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, NY (1976)"},{"issue":"1","key":"16_CR20","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1112\/blms\/5.1.85","volume":"5","author":"B Lindstr\u00f6m","year":"1973","unstructured":"Lindstr\u00f6m, B.: On the vector representations of induced matroids. Bull. London Math. Soc. 5(1), 85\u201390 (1973). https:\/\/doi.org\/10.1112\/blms\/5.1.85","journal-title":"Bull. London Math. Soc."},{"key":"16_CR21","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BFb0057377","volume-title":"Combinatorial Mathematics","author":"CHC Little","year":"1974","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. LNM, vol. 403, pp. 63\u201372. Springer, Heidelberg (1974). https:\/\/doi.org\/10.1007\/BFb0057377"},{"issue":"2","key":"16_CR22","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0095-8956(80)90066-0","volume":"28","author":"L Lov\u00e1sz","year":"1980","unstructured":"Lov\u00e1sz, L.: Matroid matching and some applications. J. Comb. Theor. Ser. B 28(2), 208\u2013236 (1980). https:\/\/doi.org\/10.1016\/0095-8956(80)90066-0","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"1","key":"16_CR23","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF01226465","volume":"31","author":"W Mader","year":"1978","unstructured":"Mader, W.: \u00dcber die Maximalzahl kreuzungsfreier $$H$$-Wege. Archiv der Mathematik 31(1), 387\u2013402 (1978). https:\/\/doi.org\/10.1007\/BF01226465","journal-title":"Archiv der Mathematik"},{"issue":"1","key":"16_CR24","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/0130017","volume":"30","author":"SB Maurer","year":"1976","unstructured":"Maurer, S.B.: Matrix generalizations of some theorems on trees, cycles and cocycles in graphs. SIAM J. Appl. Math. 30(1), 143\u2013148 (1976). https:\/\/doi.org\/10.1137\/0130017","journal-title":"SIAM J. Appl. Math."},{"issue":"4","key":"16_CR25","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1137\/S0097539791201897","volume":"24","author":"K Murota","year":"1995","unstructured":"Murota, K.: Computing the degree of determinants via combinatorial relaxation. SIAM J. Comput. 24(4), 765\u2013796 (1995)","journal-title":"SIAM J. Comput."},{"key":"16_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-540-68891-4_17","volume-title":"Integer Programming and Combinatorial Optimization","author":"JB Orlin","year":"2008","unstructured":"Orlin, J.B.: A fast, simpler algorithm for the matroid parity problem. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol. 5035, pp. 240\u2013258. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-68891-4_17"},{"issue":"3","key":"16_CR27","doi-asserted-by":"publisher","first-page":"929","DOI":"10.2307\/121059","volume":"150","author":"N Robertson","year":"1999","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Permanents, Pfaffian orientations, and even directed circuits. Ann. Math. 150(3), 929\u2013975 (1999). https:\/\/doi.org\/10.2307\/121059","journal-title":"Ann. Math."},{"key":"16_CR28","volume-title":"Combinatorial Optimization, Algorithms and Combinatorics","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization, Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)"},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"Snook, M.: Counting bases of representable matroids. Electron. J. Comb. 19(4), P41 (2012)","DOI":"10.37236\/2396"},{"issue":"68","key":"16_CR30","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1080\/14786436108243366","volume":"6","author":"HNV Temperley","year":"1961","unstructured":"Temperley, H.N.V., Fisher, M.E.: Dimer problem in statistical mechanics-an exact result. Philos. Mag. 6(68), 1061\u20131063 (1961). https:\/\/doi.org\/10.1080\/14786436108243366","journal-title":"Philos. Mag."},{"issue":"4","key":"16_CR31","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1017\/S030500410002449X","volume":"44","author":"WT Tutte","year":"1948","unstructured":"Tutte, W.T.: The dissection of equilateral triangles into equilateral triangles. Math. Proc. Camb. Philos. Soc. 44(4), 463\u2013482 (1948). https:\/\/doi.org\/10.1017\/S030500410002449X","journal-title":"Math. Proc. Camb. Philos. Soc."},{"issue":"2","key":"16_CR32","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci. 8(2), 189\u2013201 (1979). https:\/\/doi.org\/10.1016\/0304-3975(79)90044-6","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"16_CR33","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/0890-5401(89)90017-5","volume":"80","author":"VV Vazirani","year":"1989","unstructured":"Vazirani, V.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). https:\/\/doi.org\/10.1016\/0890-5401(89)90017-5","journal-title":"Inf. Comput."},{"key":"16_CR34","unstructured":"Webb, K.P.: Counting Bases. Ph.D. thesis, University of Waterloo, Waterloo, ON (2004)"},{"key":"16_CR35","doi-asserted-by":"publisher","unstructured":"Yamaguchi, Y.: Shortest disjoint $$\\cal{S}$$-paths via weighted linear matroid parity. In: Hong, S.H. (ed.) Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC \u201916). Leibniz International Proceedings in Informatics, vol. 64, pp. 63:1\u201363:13. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2016.63","DOI":"10.4230\/LIPIcs.ISAAC.2016.63"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-73879-2_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T23:07:22Z","timestamp":1620169642000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-73879-2_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030738785","9783030738792"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-73879-2_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"5 May 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Atlanta, GA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 May 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 May 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.gatech.edu\/ipco-2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"90","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"37% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"15","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the COVID-19 pandemic the conference took place virtually","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}