{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:14:40Z","timestamp":1725542080338},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642106309"},{"type":"electronic","value":"9783642106316"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-10631-6_88","type":"book-chapter","created":{"date-parts":[[2009,12,4]],"date-time":"2009-12-04T07:03:43Z","timestamp":1259910223000},"page":"872-881","source":"Crossref","is-referenced-by-count":0,"title":["Computing Large Matchings in Planar Graphs with Fixed Minimum Degree"],"prefix":"10.1007","author":[{"given":"Robert","family":"Franke","sequence":"first","affiliation":[]},{"given":"Ignaz","family":"Rutter","sequence":"additional","affiliation":[]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"88_CR1","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1006\/jagm.2000.1132","volume":"38","author":"T. Biedl","year":"2001","unstructured":"Biedl, T., Bose, P., Demaine, E., Lubiw, A.: Efficient algorithms for Petersen\u2019s theorem. J. Algorithms\u00a038, 110\u2013134 (2001)","journal-title":"J. Algorithms"},{"issue":"1\u20133","key":"88_CR2","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.disc.2004.05.003","volume":"285","author":"T. Biedl","year":"2004","unstructured":"Biedl, T., Demaine, E.D., Duncan, C.A., Fleischer, R., Kobourov, S.G.: Tight bounds on maximal and maximum matchings. Discrete Math.\u00a0285(1\u20133), 7\u201315 (2004)","journal-title":"Discrete Math."},{"key":"88_CR3","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s004930170002","volume":"21","author":"R. Cole","year":"2001","unstructured":"Cole, R., Ost, K., Schirra, S.: Edge-coloring bipartite multigraphs in O(E logD) time. Combinatorica\u00a021, 5\u201312 (2001)","journal-title":"Combinatorica"},{"key":"88_CR4","doi-asserted-by":"crossref","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. In: Proc. 19th Annu. ACM Conf. Theory Comput (STOC 1987), pp. 1\u20136 (1987)","DOI":"10.1145\/28395.28396"},{"key":"88_CR5","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1016\/j.jcss.2005.05.007","volume":"72","author":"J. Fakcharoenphol","year":"2006","unstructured":"Fakcharoenphol, J., Rao, S.: Planar graphs, negative weight, shortest paths, and near linear time. J. Comput. System Sci.\u00a072, 868\u2013889 (2006)","journal-title":"J. Comput. System Sci."},{"key":"88_CR6","unstructured":"Franke, R., Rutter, I., Wagner, D.: Computing large matchings in planar graphs with fixed minimum degree. Technical Report 2009-18, Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe(2009), http:\/\/digbib.ubka.uni-karlsruhe.de\/volltexte\/1000012970"},{"key":"88_CR7","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1112\/jlms\/s1-10.37.26","volume":"10","author":"P. Hall","year":"1935","unstructured":"Hall, P.: On representatives of subsets. Jour. London Math. Soc.\u00a010, 26\u201330 (1935)","journal-title":"Jour. London Math. Soc."},{"key":"88_CR8","volume-title":"Matching Theory","author":"L. Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. North Holland, Amsterdam (1986)"},{"key":"88_CR9","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $O(\\sqrt{|V|} \\cdot |E|)$ algorithm for finding maximum matchings in general graphs. In: Proc. 21st Annu. IEEE Sympos. Found. Comput. Sci (FOCS 1980), pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"issue":"5","key":"88_CR10","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1137\/S0097539789162997","volume":"24","author":"G.L. Miller","year":"1995","unstructured":"Miller, G.L., Naor, J.: Flow in planar graphs with multiple sources and sinks. SIAM J. Comput.\u00a024(5), 1002\u20131017 (1995)","journal-title":"SIAM J. Comput."},{"key":"88_CR11","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: Proc. 45th Annu. IEEE Sympos. Foundat. Comput. Sci (FOCS 2004), pp. 248\u2013255 (2004)","DOI":"10.1109\/FOCS.2004.40"},{"issue":"1","key":"88_CR12","doi-asserted-by":"publisher","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\u00a045(1), 3\u201320 (2006)","journal-title":"Algorithmica"},{"issue":"3","key":"88_CR13","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0012-365X(79)90133-X","volume":"28","author":"T. Nishizeki","year":"1979","unstructured":"Nishizeki, T., Baybars, I.: Lower bounds on the cardinality of the maximum matchings of planar graphs. Discrete Math.\u00a028(3), 255\u2013267 (1979)","journal-title":"Discrete Math."},{"key":"88_CR14","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Worst-case ratios for planar graphs and the method of induction on faces. In: Proc. 22nd Annu. IEEE Sympos. Foundat. Comput. Sci (FOCS 1981), pp. 358\u2013363 (1981)","DOI":"10.1109\/SFCS.1981.55"},{"key":"88_CR15","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF02392606","volume":"15","author":"J. Petersen","year":"1891","unstructured":"Petersen, J.: Die Theorie der regul\u00e4ren Graphs. Acta Mathematica\u00a015, 193\u2013220 (1891)","journal-title":"Acta Mathematica"},{"key":"88_CR16","unstructured":"Rutter, I., Wolff, A.: Computing large matchings fast. In: Proc. 19th Annu. ACM-SIAM Sympos. Discr. Algorithms (SODA 2008), pp. 183\u2013192 (2008)"},{"key":"88_CR17","doi-asserted-by":"crossref","unstructured":"Rutter, I., Wolff, A.: Computing large matchings fast. Transactions on Algorithms (to appear)","DOI":"10.1145\/1868237.1868238"},{"key":"88_CR18","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1137\/S0097539796299266","volume":"28","author":"A. Schrijver","year":"1999","unstructured":"Schrijver, A.: Bipartite edge coloring in O(\u0394m) time. SIAM J. Comput.\u00a028, 841\u2013846 (1999)","journal-title":"SIAM J. Comput."},{"key":"88_CR19","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data structures and network algorithms","author":"R.E. Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Data structures and network algorithms. SIAM, Philadelphia (1983)"},{"key":"88_CR20","doi-asserted-by":"publisher","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.\u00a022, 107\u2013111 (1947)","journal-title":"J. Lond. Math. Soc."},{"key":"88_CR21","unstructured":"Yuster, R., Zwick, U.: Maximum matching in graphs with an exluded minor. In: Proc. 18th Annu. ACM-SIAM Sympos. Discr. Algorithms (SODA 2007), pp. 108\u2013117 (2007)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-10631-6_88.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:32:28Z","timestamp":1606185148000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-10631-6_88"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642106309","9783642106316"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-10631-6_88","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}