{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T16:08:51Z","timestamp":1743005331285,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319193144"},{"type":"electronic","value":"9783319193151"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19315-1_12","type":"book-chapter","created":{"date-parts":[[2015,6,6]],"date-time":"2015-06-06T10:42:08Z","timestamp":1433587328000},"page":"128-139","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Solving Matching Problems Efficiently in Bipartite Graphs"],"prefix":"10.1007","author":[{"given":"Selma","family":"Djelloul","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,7]]},"reference":[{"issue":"4","key":"12_CR1","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0020-0190(91)90195-N","volume":"37","author":"H Alt","year":"1991","unstructured":"Alt, H., Blum, N., Mehlhorn, K., Paul, M.: Computing a maximum cardinality matching in a bipartite graph in time $${O}(n^{1.5}\\sqrt{m\/\\log n})$$. Inf. Process. Lett. 37(4), 237\u2013240 (1991)","journal-title":"Inf. Process. Lett."},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0012-365X(00)00061-3","volume":"223","author":"AS Asratian","year":"2000","unstructured":"Asratian, A.S.: Some results on an edge-coloring problem of Folkman and Fulkerson. Discret. Math. 223, 13\u201325 (2000)","journal-title":"Discret. Math."},{"key":"12_CR3","volume-title":"A First Course in Graph Theory","author":"G Chartrand","year":"2012","unstructured":"Chartrand, G., Zhang, P.: A First Course in Graph Theory. Dover Publications, New York (2012)"},{"issue":"1","key":"12_CR4","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 \\log D)}$$ time. Combinatorica 21(1), 5\u201312 (2001)","journal-title":"Combinatorica"},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1007\/s00224-012-9410-7","volume":"52","author":"JF Couturier","year":"2013","unstructured":"Couturier, J.F., Golovach, P.A., Kratsch, D., Liedloff, M., Pyatkin, A.: Colorings with few colors: counting, enumeration and combinatorial bounds. Theory Comput. Syst. 52, 645\u2013667 (2013). Springer-Verlag New York. Secaucus, NJ, USA","journal-title":"Theory Comput. Syst."},{"issue":"5","key":"12_CR6","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1002\/jgt.3190150508","volume":"15","author":"G Ding","year":"1991","unstructured":"Ding, G.: Covering the edges with consecutive sets. J. Graph Theory 15(5), 559\u2013562 (1991)","journal-title":"J. Graph Theory"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Even, S., Kariv, O.: An $${O}(n^{2.5})$$ algorithm for maximum matching in general graphs. In: IEEE 16th annual Symposium on Foundations of Computer Science (FOCS), pp. 100\u2013112 (1975)","DOI":"10.1109\/SFCS.1975.5"},{"key":"12_CR8","first-page":"561","volume-title":"Combinatorial Mathematics and its Applications","author":"J Folkman","year":"1969","unstructured":"Folkman, J., Fulkerson, D.R.: Edge-colorings in bipartite graphs. In: Bose, R., Dowling, T. (eds.) Combinatorial Mathematics and its Applications, pp. 561\u2013577. University of North Carolina Press, Chapel Hill (1969)"},{"key":"12_CR9","first-page":"283","volume":"29","author":"H Frost","year":"1990","unstructured":"Frost, H., Jacobson, M., Kabell, J., Morris, F.R.: Bipartite analogues of split graphs and related topics. Ars Combinatoria 29, 283\u2013288 (1990)","journal-title":"Ars Combinatoria"},{"issue":"2","key":"12_CR10","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1002\/jgt.3190020209","volume":"2","author":"MR Golumbic","year":"1978","unstructured":"Golumbic, M.R., Goss, C.F.: Perfect elimination and chordal bipartite graphs. J. Graph Theory 2(2), 155\u2013163 (1978)","journal-title":"J. Graph Theory"},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0166-218X(90)90092-Q","volume":"28","author":"PL Hammer","year":"1990","unstructured":"Hammer, P.L., Peled, U.N., Sun, X.: Difference graphs. Discret. Appl. Math. 28, 35\u201344 (1990)","journal-title":"Discret. Appl. Math."},{"key":"12_CR12","first-page":"87","volume":"14","author":"P Heggernes","year":"2007","unstructured":"Heggernes, P., Kratsch, D.: Linear-time certifying recognition algorithms and forbidden induced subgraphs. Nordic J. Comput. 14, 87\u2013108 (2007)","journal-title":"Nordic J. Comput."},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0012-365X(90)90387-W","volume":"85","author":"K Heinrich","year":"1990","unstructured":"Heinrich, K., Hell, P., Kirkpatrick, D.G., Liu, G.: A simple existence criterion for ($$g<f$$)-factors. Discrete Mathematics 85, 313\u2013317 (1990)","journal-title":"Discrete Mathematics"},{"issue":"4","key":"12_CR14","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"12_CR15","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.jctb.2011.07.004","volume":"102","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y., Reed, B.: The disjoint paths problem in quadratic time. J. Comb. Theory Ser. B 102, 424\u2013435 (2012)","journal-title":"J. Comb. Theory Ser. B"},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"3733","DOI":"10.1016\/j.tcs.2009.05.005","volume":"410","author":"L Kowalik","year":"2009","unstructured":"Kowalik, L.: Improved edge-coloring with three colors. Theoret. Comput. Sci. 410, 3733\u20133742 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/978-3-642-11409-0_26","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Y Okamoto","year":"2010","unstructured":"Okamoto, Y., Uehara, R., Uno, T.: Counting the number of matchings in chordal and chordal bipartite graph classes. In: Paul, C., Habib, M. (eds.) WG 2009. LNCS, vol. 5911, pp. 296\u2013307. Springer, Heidelberg (2010)"},{"key":"12_CR18","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 graphen. Acta Mathematica 15, 193\u2013220 (1891)","journal-title":"Acta Mathematica"},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"Robertson, N., Sanders, D., Seymour, P., Thomas, R.: Efficiently four-coloring planar graphs. In: Proceedings of the 28th annual ACM Symposium on Theory of Computing, (STOC), pp. 571\u2013575 (1996)","DOI":"10.1145\/237814.238005"},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1006\/jctb.1997.1752","volume":"70","author":"N Robertson","year":"1997","unstructured":"Robertson, N., Seymour, P., Thomas, R.: Tutte\u2019s edge-coloring conjecture. J. Comb. Theory Ser. B 70, 166\u2013183 (1997)","journal-title":"J. Comb. Theory Ser. B"},{"key":"12_CR21","volume-title":"Combinatorial Optimization","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization, vol. 1. Springer-Verlag, Berlin (2003)"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1016\/0095-8956(78)90009-6","volume":"25","author":"P Slater","year":"1978","unstructured":"Slater, P.: A constructive characterization of trees with at least $$k$$ disjoint maximum matchings. J. Comb. Theory Ser. B 25, 326\u2013338 (1978)","journal-title":"J. Comb. Theory Ser. B"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Thomas, R.: Recent excluded minor theorem for graphs. In: Surveys in Combinatorics, vol. 267, pp. 201\u2013222 (1999). The electronic journal of combinatorics 8 (2001)","DOI":"10.1017\/CBO9780511721335.008"},{"issue":"2","key":"12_CR24","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Node deletion problems on bipartite graphs. SIAM J. Comput. 10(2), 310\u2013327 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19315-1_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T08:24:24Z","timestamp":1676017464000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19315-1_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319193144","9783319193151"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19315-1_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"7 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}