{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T06:17:17Z","timestamp":1725862637962},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662531730"},{"type":"electronic","value":"9783662531747"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53174-7_27","type":"book-chapter","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T10:50:06Z","timestamp":1470307806000},"page":"373-387","source":"Crossref","is-referenced-by-count":1,"title":["Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs"],"prefix":"10.1007","author":[{"given":"Kenjiro","family":"Takazawa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,5]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/s00453-012-9642-6","volume":"64","author":"MA Babenko","year":"2012","unstructured":"Babenko, M.A.: Improved algorithms for even factors and square-free simple $$b$$ -matchings. Algorithmica 64, 362\u2013383 (2012)","journal-title":"Algorithmica"},{"key":"27_CR2","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1016\/j.jctb.2011.08.007","volume":"102","author":"K B\u00e9rczi","year":"2012","unstructured":"B\u00e9rczi, K., Kobayashi, Y.: An algorithm for $$(n-3)$$ -connectivity augmentation problem: Jump system approach. J. Comb. Theor. Ser. B 102, 565\u2013587 (2012)","journal-title":"J. Comb. Theor. Ser. B"},{"key":"27_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/978-3-642-13036-6_4","volume-title":"Integer Programming and Combinatorial Optimization","author":"K B\u00e9rczi","year":"2010","unstructured":"B\u00e9rczi, K., V\u00e9gh, L.A.: Restricted b-matchings in degree-bounded graphs. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 43\u201356. Springer, Heidelberg (2010)"},{"key":"27_CR4","first-page":"258","volume":"247","author":"C Berge","year":"1958","unstructured":"Berge, C.: Sur le couplage maximum d\u2019un graphe. Comptes Rendus Hebdomadaires S\u00e9ances l\u2019de Acad\u00e9mie de Sciences 247, 258\u2013259 (1958)","journal-title":"Comptes Rendus Hebdomadaires S\u00e9ances l\u2019de Acad\u00e9mie de Sciences"},{"key":"27_CR5","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1137\/S0895480191222926","volume":"8","author":"A Bouchet","year":"1995","unstructured":"Bouchet, A., Cunningham, W.H.: Delta-matroids, jump systems, and bisubmodular polyhedra. SIAM J. Discrete Math. 8, 17\u201332 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"27_CR6","doi-asserted-by":"crossref","first-page":"918","DOI":"10.1137\/110843514","volume":"27","author":"S Boyd","year":"2013","unstructured":"Boyd, S., Iwata, S., Takazawa, K.: Finding 2-factors closer to TSP tours in cubic graphs. SIAM J. Discrete Math. 27, 918\u2013939 (2013)","journal-title":"SIAM J. Discrete Math."},{"key":"27_CR7","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/s10107-012-0620-1","volume":"144","author":"S Boyd","year":"2014","unstructured":"Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: The traveling salesman problem on cubic and subcubic graphs. Math. Program. 144, 227\u2013245 (2014)","journal-title":"Math. Program."},{"key":"27_CR8","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0012-365X(80)90002-3","volume":"29","author":"G Cornu\u00e9jols","year":"1980","unstructured":"Cornu\u00e9jols, G., Pulleyblank, W.: A matching problem with side conditions. Discrete Math. 29, 135\u2013159 (1980)","journal-title":"Discrete Math."},{"key":"27_CR9","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1137\/140972925","volume":"29","author":"JR Correa","year":"2015","unstructured":"Correa, J.R., Larr\u00e9, O., Soto, J.A.: TSP tours in cubic graphs: beyond 4\/3. SIAM J. Discrete Math. 29, 915\u2013939 (2015)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"27_CR10","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/s101070100256","volume":"91","author":"WH Cunningham","year":"2002","unstructured":"Cunningham, W.H.: Matching, matroids, and extensions. Math. Program. 91(3), 515\u2013542 (2002)","journal-title":"Math. Program."},{"key":"27_CR11","first-page":"393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. Oper. Res. 2, 393\u2013410 (1954)","journal-title":"Oper. Res."},{"key":"27_CR12","doi-asserted-by":"crossref","first-page":"517","DOI":"10.4153\/CJM-1958-052-0","volume":"10","author":"AL Dulmage","year":"1958","unstructured":"Dulmage, A.L., Mendelsohn, N.S.: Coverings of bipartite graphs. Can. J. Math. 10, 517\u2013534 (1958)","journal-title":"Can. J. Math."},{"key":"27_CR13","unstructured":"Dulmage, A.L., Mendelsohn, N.S.: A structure theory of bipartite graphs of finite exterior dimension. Trans. Roy. Soc. Can. Sect. III 53, 1\u201313 (1959)"},{"key":"27_CR14","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":"27_CR15","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0166-218X(02)00461-4","volume":"131","author":"A Frank","year":"2003","unstructured":"Frank, A.: Restricted $$t$$ -matchings in bipartite graphs. Discrete Appl. Math. 131, 337\u2013346 (2003)","journal-title":"Discrete Appl. Math."},{"key":"27_CR16","first-page":"373","volume":"8","author":"T Gallai","year":"1963","unstructured":"Gallai, T.: Kritische Graphen II. A Magyar Tudom\u00e1nyos Akad\u00e9mia\u2014Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei 8, 373\u2013395 (1963)","journal-title":"A Magyar Tudom\u00e1nyos Akad\u00e9mia\u2014Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei"},{"key":"27_CR17","first-page":"401","volume":"9","author":"T Gallai","year":"1964","unstructured":"Gallai, T.: Maximale Systeme unabh\u00e4nginger Kanten. A Magyar Tudom\u00e1nyos Akad\u00e9mia\u2014Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei 9, 401\u2013413 (1964)","journal-title":"A Magyar Tudom\u00e1nyos Akad\u00e9mia\u2014Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei"},{"key":"27_CR18","unstructured":"Geelen, J.F.: The $$C_6$$ -free $$2$$ -factor problem in bipartite graphs is NP-complete (1999), unpublished"},{"key":"27_CR19","unstructured":"Hartvigsen, D.: Extensions of matching theory. Ph.D. thesis. Carnegie Mellon University (1984)"},{"key":"27_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1007\/3-540-48777-8_18","volume-title":"Integer Programming and Combinatorial Optimization","author":"D Hartvigsen","year":"1999","unstructured":"Hartvigsen, D.: The square-free 2-factor problem in bipartite graphs. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol. 1610, pp. 234\u2013241. Springer, Heidelberg (1999)"},{"key":"27_CR21","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1016\/j.jctb.2006.01.004","volume":"96","author":"D Hartvigsen","year":"2006","unstructured":"Hartvigsen, D.: Finding maximum square-free 2-matchings in bipartite graphs. J. Comb. Theor. Ser. B 96, 693\u2013705 (2006)","journal-title":"J. Comb. Theor. Ser. B"},{"key":"27_CR22","first-page":"1027","volume":"21","author":"D Hartvigsen","year":"2011","unstructured":"Hartvigsen, D., Li, Y.: Maximum cardinality simple $$2$$ -matchings in subcubic graphs. SIAM J. Discrete Math. 21, 1027\u20131045 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"27_CR23","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s10107-012-0516-0","volume":"138","author":"D Hartvigsen","year":"2013","unstructured":"Hartvigsen, D., Li, Y.: Polyhedron of triangle-free simple $$2$$ -matchings in subcubic graphs. Math. Program. 138, 43\u201382 (2013)","journal-title":"Math. Program."},{"key":"27_CR24","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/B978-0-12-566780-7.50018-0","volume-title":"Progress in Combinatorial Optimization","author":"M Iri","year":"1984","unstructured":"Iri, M.: Structural theory for the combinatorial systems characterized by submodular functions. In: Pulleyblank, W.R. (ed.) Progress in Combinatorial Optimization, pp. 197\u2013219. Academic Press, New York (1984)"},{"key":"27_CR25","unstructured":"Karp, J.A., Ravi, R.: A $$9\/7$$ -approximation algorithm for graphic TSP in cubic bipartite graphs. In: Jansen, K., Rolim, J., Devanur, N., Moore, C. (eds.) Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, pp. 284\u2013296 (2014)"},{"key":"27_CR26","unstructured":"Kir\u00e1ly, Z.: $$C_4$$ -free $$2$$ -factors in bipartite graphs. Technical report, TR-2001-13, Egerv\u00e1ry Research Group (1999)"},{"key":"27_CR27","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.disopt.2010.04.001","volume":"7","author":"Y Kobayashi","year":"2010","unstructured":"Kobayashi, Y.: A simple algorithm for finding a maximum triangle-free $$2$$ -matching in subcubic graphs. Discrete Optim. 7, 197\u2013202 (2010)","journal-title":"Discrete Optim."},{"key":"27_CR28","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.dam.2014.05.016","volume":"175","author":"Y Kobayashi","year":"2014","unstructured":"Kobayashi, Y.: Triangle-free $$2$$ -matchings and M-concave functions on jump systems. Discrete Appl. Math. 175, 35\u201342 (2014)","journal-title":"Discrete Appl. Math."},{"key":"27_CR29","doi-asserted-by":"crossref","first-page":"948","DOI":"10.1016\/j.jctb.2012.03.003","volume":"102","author":"Y Kobayashi","year":"2012","unstructured":"Kobayashi, Y., Szab\u00f3, J., Takazawa, K.: A proof of Cunningham\u2019s conjecture on restricted subgraphs and jump systems. J. Comb. Theor. Ser. B 102, 948\u2013966 (2012)","journal-title":"J. Comb. Theor. Ser. B"},{"key":"27_CR30","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/j.disopt.2012.02.003","volume":"9","author":"Y Kobayashi","year":"2012","unstructured":"Kobayashi, Y., Yin, X.: An algorithm for finding a maximum $$t$$ -matching excluding complete partite subgraphs. Discrete Optim. 9, 98\u2013108 (2012)","journal-title":"Discrete Optim."},{"key":"27_CR31","first-page":"116","volume":"38","author":"D K\u0151nig","year":"1931","unstructured":"K\u0151nig, D.: Graphok \u00e9s matrixok. Matematikai \u00e9s Fizikai Lapok 38, 116\u2013119 (1931)","journal-title":"Matematikai \u00e9s Fizikai Lapok"},{"key":"27_CR32","doi-asserted-by":"crossref","DOI":"10.1090\/chel\/367","volume-title":"Matching Theory","author":"L Lov\u00e1sz","year":"2009","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. AMS Chelsea Publishing, Providence (2009)"},{"key":"27_CR33","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1137\/060652282","volume":"21","author":"M Makai","year":"2007","unstructured":"Makai, M.: On maximum cost $$K_{t, t}$$ -free $$t$$ -matchings of bipartite graphs. SIAM J. Discrete Math. 21, 349\u2013360 (2007)","journal-title":"SIAM J. Discrete Math."},{"key":"27_CR34","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1137\/040618710","volume":"20","author":"K Murota","year":"2006","unstructured":"Murota, K.: M-convex functions on jump systems: A general framework for minsquare graph factor problem. SIAM J. Discrete Math. 20, 226\u2013231 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"27_CR35","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-03994-2","volume-title":"Matrices and Matroids for Systems Analysis","author":"K Murota","year":"2010","unstructured":"Murota, K.: Matrices and Matroids for Systems Analysis. Springer, Heidelberg (2010). softcover edn"},{"key":"27_CR36","unstructured":"Pap, G.: Alternating paths revisited II: Restricted $$b$$ -matchings in bipartite graphs. Technical report, TR-2005-13. Egerv\u00e1ry Research Group (2005)"},{"key":"27_CR37","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s10107-006-0053-9","volume":"110","author":"G Pap","year":"2007","unstructured":"Pap, G.: Combinatorial algorithms for matchings, even factors and square-free 2-factors. Math. Program. 110, 57\u201369 (2007)","journal-title":"Math. Program."},{"key":"27_CR38","volume-title":"Combinatorial Optimization\u2014Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization\u2014Polyhedra and Efficiency. Springer, Heidelberg (2003)"},{"key":"27_CR39","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1287\/moor.1080.0365","volume":"34","author":"K Takazawa","year":"2009","unstructured":"Takazawa, K.: A weighted $$K_{t, t}$$ -free $$t$$ -factor algorithm for bipartite graphs. Math. Oper. Res. 34, 351\u2013362 (2009)","journal-title":"Math. Oper. Res."},{"key":"27_CR40","volume-title":"Approximation algorithms for the minimum $$2$$ -edge connected spanning subgraph problem and the graph-TSP in regular bipartite graphs via restricted $$2$$ -factors, Preprint, RIMS-1826","author":"K Takazawa","year":"2015","unstructured":"Takazawa, K.: Approximation algorithms for the minimum $$2$$ -edge connected spanning subgraph problem and the graph-TSP in regular bipartite graphs via restricted $$2$$ -factors, Preprint, RIMS-1826. Kyoto University, Research Institute for Mathematical Sciences (2015)"},{"key":"27_CR41","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"22","author":"WT 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."},{"key":"27_CR42","unstructured":"Vornberger, O.: Easy and hard cycle covers, Preprint, Universit\u00e4t Paderborn (1980)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53174-7_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T15:57:46Z","timestamp":1498319866000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53174-7_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531730","9783662531747"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53174-7_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}