{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:49:08Z","timestamp":1770994148972,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2012,2,8]],"date-time":"2012-02-08T00:00:00Z","timestamp":1328659200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2013,4]]},"DOI":"10.1007\/s10107-012-0516-0","type":"journal-article","created":{"date-parts":[[2012,2,7]],"date-time":"2012-02-07T19:48:39Z","timestamp":1328644119000},"page":"43-82","source":"Crossref","is-referenced-by-count":13,"title":["Polyhedron of triangle-free simple 2-matchings in subcubic graphs"],"prefix":"10.1007","volume":"138","author":[{"given":"David","family":"Hartvigsen","sequence":"first","affiliation":[]},{"given":"Yanjun","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,2,8]]},"reference":[{"key":"516_CR1","first-page":"258","volume":"247","author":"C. Berge","year":"1958","unstructured":"Berge C.: Sur le couplate maximum d\u2019un graphe. Comptes Rendus Hebdomadaires des S\u00e9ances de l\u2019Acad\u00e9mie Sciences [Paris] 247, 258\u2013259 (1958)","journal-title":"Comptes Rendus Hebdomadaires des S\u00e9ances de l\u2019Acad\u00e9mie Sciences [Paris]"},{"key":"516_CR2","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/S089548019427144X","volume":"10","author":"E. Bertram","year":"1997","unstructured":"Bertram E., Horak P.: Decomposing 4-regular graphs into triangle-free 2-factors. SIAM J. Discrete Math. 10, 309\u2013317 (1997)","journal-title":"SIAM J. Discrete Math."},{"key":"516_CR3","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01580109","volume":"5","author":"V. Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal V.: Edmonds polytopes and weakly hamiltonian graphs. Math. Prog. 5, 29\u201340 (1973)","journal-title":"Math. Prog."},{"key":"516_CR4","volume-title":"Combinatorial Optimization","author":"W.J. Cook","year":"1998","unstructured":"Cook W.J., Cunningham W.H., Pulleyblank W.R., Schrijver A.: Combinatorial Optimization. Wiley, New York (1998)"},{"key":"516_CR5","first-page":"383","volume":"32","author":"G. Cornu\u00e9jols","year":"1985","unstructured":"Cornu\u00e9jols G., Naddef D., Pulleyblank W.R.: The traveling salesman problem in graphs with 3-edge cutsets. J.A.C.M. 32, 383\u2013410 (1985)","journal-title":"J.A.C.M."},{"key":"516_CR6","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.R.: A matching problem with side constraints. Discrete Math. 29, 135\u2013159 (1980)","journal-title":"Discrete Math."},{"key":"516_CR7","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s101079900110","volume":"87","author":"W.H. Cunningham","year":"2000","unstructured":"Cunningham W.H., Wang Y.: Restricted 2-factor polytopes. Math. Prog. 87, 87\u2013111 (2000)","journal-title":"Math. Prog."},{"key":"516_CR8","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":"516_CR9","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69","author":"J. Edmonds","year":"1965","unstructured":"Edmonds J.: Maximum matching and a polyhedron with 0, 1 vertices. J. Res. Natl. Bur. Stand. 69, 125\u2013130 (1965)","journal-title":"J. Res. Natl. Bur. Stand."},{"key":"516_CR10","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1287\/opre.27.4.799","volume":"27","author":"M.L. Fisher","year":"1979","unstructured":"Fisher M.L., Nemhauser G.L., Wolsey L.A.: An analysis of approximations for finding a maximum weight Hamiltonian circuit. Oper. Res. 27, 799\u2013809 (1979)","journal-title":"Oper. Res."},{"key":"516_CR11","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing. The Association for Computing Machinery, New York, pp. 448\u2013456 (1983)","DOI":"10.1145\/800061.808776"},{"key":"516_CR12","first-page":"282","volume":"16","author":"M. Gr\u00f6tschel","year":"1979","unstructured":"Gr\u00f6tschel M., Padberg M.W.: On the symmetric traveling salesman problem II: lifting theorems and facets. Math. Prog. 16, 282\u2013302 (1979)","journal-title":"Math. Prog."},{"key":"516_CR13","unstructured":"Hartvigsen, D.: Extensions of matching theory. Ph.D. Thesis, Carnegie-Mellon University (1984); under the supervision of G\u00e9rard Cornu\u00e9jols"},{"key":"516_CR14","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. Theory B 96, 693\u2013705 (2006)","journal-title":"J. Comb. Theory B"},{"key":"516_CR15","unstructured":"Hartvigsen, D., Li, Y.: Maximum cardinality simple 2-matchings in subcubic graphs. SIAM J. Optimization V. 21, No. 3, 1027\u20131045 (2011)"},{"key":"516_CR16","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1137\/0401046","volume":"1","author":"P. Hell","year":"1988","unstructured":"Hell P., Kirkpatrick D., Kratochv\u00edl J., K\u0155\u00ed\u017a I.: On restricted 2-factors. SIAM J. Discrete Math. 1, 472\u2013484 (1988)","journal-title":"SIAM J. Discrete Math."},{"key":"516_CR17","first-page":"111","volume":"20","author":"D. Holton","year":"1999","unstructured":"Holton D., Aldred R.E.L.: Planar graphs, regular graphs, bipartite graphs and Hamiltonicity. Australas. J. Comb. 20, 111\u2013131 (1999)","journal-title":"Australas. J. Comb."},{"key":"516_CR18","doi-asserted-by":"crossref","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, 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"516_CR19","unstructured":"Johnson, E.: Network flows, graphs and integer programming. Ph.D. Thesis, University of California, Berkeley (1965)"},{"key":"516_CR20","doi-asserted-by":"crossref","unstructured":"Kaiser, T., Skrekovski, R.: Cycles intersecting cuts of prescribed sizes. Manuscript (2005)","DOI":"10.46298\/dmtcs.3465"},{"key":"516_CR21","volume-title":"The Traveling Salesman Problem\u2014A Guided Tour of Combinatorial Optimization","author":"E.L. Lawler","year":"1985","unstructured":"Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B.: The Traveling Salesman Problem\u2014A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)"},{"key":"516_CR22","unstructured":"Nam, Y.: Matching Theory: Subgraphs with degree constraints and other properties. Ph.D. Thesis, University of British Columbia (1994); Under the supervision of R. Anstee"},{"key":"516_CR23","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. Prog. 110, 57\u201369 (2007)","journal-title":"Math. Prog."},{"key":"516_CR24","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF02392606","volume":"15","author":"J. Petersen","year":"1891","unstructured":"Petersen J.: Die Theorie der regul\u00e4ren graphs. Acta Math. 15, 193\u2013220 (1891)","journal-title":"Acta Math."},{"key":"516_CR25","first-page":"225","volume":"5","author":"J. Petersen","year":"1898","unstructured":"Petersen J.: Sur le theoreme de Tait. L\u2019Intermediaire des Mathematiciens 5, 225\u2013227 (1898)","journal-title":"L\u2019Intermediaire des Mathematiciens"},{"key":"516_CR26","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1006\/jctb.1997.1750","volume":"70","author":"N. Robertson","year":"1997","unstructured":"Robertson N., Sanders D., Seymour P., Thomas R.: The four colour theorem. J. Comb. Theory B 70, 2\u201344 (1997)","journal-title":"J. Comb. Theory B"},{"key":"516_CR27","volume-title":"Combinatorial Optimization, Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver A.: Combinatorial Optimization, Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"516_CR28","doi-asserted-by":"crossref","unstructured":"Tait, P.G.: Remarks on the previous communication. Proc. R. Soc. Edinburgh 10, 729 (1878\u20131880)","DOI":"10.1017\/S0370164600044643"},{"key":"516_CR29","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."},{"key":"516_CR30","doi-asserted-by":"crossref","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"W.T. Tutte","year":"1954","unstructured":"Tutte W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6, 347\u2013352 (1954)","journal-title":"Can. J. Math."},{"key":"516_CR31","unstructured":"Vornberger, O.: Easy and hard cycle covers. Manuscript, Universit\u00e4t Paderborn (1980)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-012-0516-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-012-0516-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-012-0516-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,28]],"date-time":"2021-12-28T04:30:00Z","timestamp":1640665800000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-012-0516-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,8]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["516"],"URL":"https:\/\/doi.org\/10.1007\/s10107-012-0516-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,8]]}}}