{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T04:37:18Z","timestamp":1716352638169},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2011,4,30]],"date-time":"2011-04-30T00:00:00Z","timestamp":1304121600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00453-011-9519-0","type":"journal-article","created":{"date-parts":[[2011,4,29]],"date-time":"2011-04-29T17:26:47Z","timestamp":1304098007000},"page":"39-50","source":"Crossref","is-referenced-by-count":8,"title":["Almost Exact Matchings"],"prefix":"10.1007","volume":"63","author":[{"given":"Raphael","family":"Yuster","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,4,30]]},"reference":[{"issue":"4","key":"9519_CR1","doi-asserted-by":"crossref","first-page":"801","DOI":"10.1090\/S0894-0347-1990-1065053-0","volume":"3","author":"N. Alon","year":"1990","unstructured":"Alon, N., Seymour, P.D., Thomas, R.: A separator theorem for nonplanar graphs. J. Am. Math. Soc. 3(4), 801\u2013808 (1990)","journal-title":"J. Am. Math. Soc."},{"key":"9519_CR2","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(85)90222-1","volume":"38","author":"T. Asano","year":"1985","unstructured":"Asano, T.: An approach to the subgraph homeomorphism problem. Theor. Comput. Sci. 38, 249\u2013267 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"9519_CR3","first-page":"273","volume-title":"Proc. of 13th IPCO","author":"A. Berger","year":"2008","unstructured":"Berger, A., Bonifaci, V., Grandoni, F., Sch\u00e4fer, G.: Budgeted matching and budgeted matroid intersection via the gasoline puzzle. In: Proc. of 13th IPCO, pp. 273\u2013287 (2008)"},{"key":"9519_CR4","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"issue":"4","key":"9519_CR5","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"H.N. Gabow","year":"1991","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph matching problems. J. ACM 38(4), 815\u2013853 (1991)","journal-title":"J. ACM"},{"key":"9519_CR6","volume":"6","author":"A. Galluccio","year":"1999","unstructured":"Galluccio, A., Loebl, M.: On the theory of Pfaffian orientations. I. Perfect matchings and permanents. Electron. J. Comb. 6, #R6 (1999)","journal-title":"Electron. J. Comb."},{"key":"9519_CR7","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1137\/0710032","volume":"10","author":"A. George","year":"1973","unstructured":"George, A.: Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10, 345\u2013363 (1973)","journal-title":"SIAM J. Numer. Anal."},{"issue":"4","key":"9519_CR8","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/BF01396660","volume":"50","author":"J.R. Gilbert","year":"1987","unstructured":"Gilbert, J.R., Tarjan, R.E.: The analysis of a nested dissection algorithm. Numer. Math. 50(4), 377\u2013404 (1987)","journal-title":"Numer. Math."},{"issue":"3","key":"9519_CR9","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput. 2(3), 135\u2013158 (1973)","journal-title":"SIAM J. Comput."},{"key":"9519_CR10","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02579407","volume":"6","author":"R. Karp","year":"1986","unstructured":"Karp, R., Upfal, E., Wigderson, A.: Constructing a perfect matching is in random NC. Combinatorica 6, 35\u201348 (1986)","journal-title":"Combinatorica"},{"key":"9519_CR11","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: Graph Theory and Theoretical Physics, pp.\u00a043\u2013110. Academic Press, London (1967)"},{"issue":"2","key":"9519_CR12","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Rose, D.J., Tarjan, R.E.: Generalized nested dissection. SIAM J. Numer. Anal. 16(2), 346\u2013358 (1979)","journal-title":"SIAM J. Numer. Anal."},{"issue":"2","key":"9519_CR13","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"9519_CR14","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/BFb0057377","volume-title":"Combinatorial Mathematics, Proc. 2nd Australian Conference","author":"C.H.C. 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. (ed.) Combinatorial Mathematics, Proc. 2nd Australian Conference. Lecture Notes in Mathematics, vol. 403, pp. 63\u201372 (1974)"},{"key":"9519_CR15","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00453-005-1187-5","volume":"45","author":"M. Mucha","year":"2006","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings in planar graphs via Gaussian elimination. Algorithmica 45, 3\u201320 (2006)","journal-title":"Algorithmica"},{"issue":"1","key":"9519_CR16","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105\u2013113 (1987)","journal-title":"Combinatorica"},{"issue":"2","key":"9519_CR17","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1145\/322307.322309","volume":"29","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The complexity of restricted spanning tree problems. J. ACM 29(2), 285\u2013309 (1982)","journal-title":"J. ACM"},{"key":"9519_CR18","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"22","author":"W.T. Tutte","year":"1947","unstructured":"Tutte, W.T.: The factorization of linear graphs. J. Lond. Math. Soc. 22, 107\u2013111 (1947)","journal-title":"J. Lond. Math. Soc."},{"issue":"2","key":"9519_CR19","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 3,3-free graphs and related problems. Inf. Comput. 80(2), 152\u2013164 (1989)","journal-title":"Inf. Comput."},{"key":"9519_CR20","first-page":"108","volume-title":"Proc. of 18th SODA","author":"R. Yuster","year":"2007","unstructured":"Yuster, R., Zwick, U.: Maximum matching in graphs with an excluded minor. In: Proc. of 18th SODA, pp. 108\u2013117 (2007)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9519-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9519-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9519-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:07Z","timestamp":1559137507000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9519-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4,30]]},"references-count":20,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9519"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9519-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4,30]]}}}