{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T07:02:18Z","timestamp":1772953338677,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2012,12,21]],"date-time":"2012-12-21T00:00:00Z","timestamp":1356048000000},"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":[[2014,4]]},"DOI":"10.1007\/s10107-012-0620-1","type":"journal-article","created":{"date-parts":[[2012,12,20]],"date-time":"2012-12-20T11:18:41Z","timestamp":1356002321000},"page":"227-245","source":"Crossref","is-referenced-by-count":24,"title":["The traveling salesman problem on cubic and subcubic graphs"],"prefix":"10.1007","volume":"144","author":[{"given":"Sylvia","family":"Boyd","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ren\u00e9","family":"Sitters","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suzanne","family":"van der Ster","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,12,21]]},"reference":[{"key":"620_CR1","unstructured":"Aggarwal, N., Garg, N., Gupta, S.: A 4\/3-approximation for TSP on cubic 3-edge-connected graphs. Tech. Rep. (2011). http:\/\/arxiv.org\/abs\/1101.5586"},{"key":"620_CR2","first-page":"73","volume":"3","author":"T Akiyama","year":"1980","unstructured":"Akiyama, T., Nishizeki, T., Saito, N.: NP-completeness of the Hamiltonian cycle problem for bipartite graphs. J. Inf. Process. 3, 73\u201376 (1980)","journal-title":"J. Inf. Process."},{"key":"620_CR3","unstructured":"Arora, S., Grigni, M., Karger, D., Klein, P., Woloszyn, A.: A polynomial-time approximation scheme for weighted planar graph TSP. In: Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, pp. 33\u201341 (1998)"},{"key":"620_CR4","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1137\/S0895480102409619","volume":"17","author":"F Barahona","year":"2004","unstructured":"Barahona, F.: Fractional packing of t-joins. SIAM J. Discret. Math. 17, 661\u2013669 (2004)","journal-title":"SIAM J. Discret. Math."},{"key":"620_CR5","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1287\/moor.1080.0337","volume":"33","author":"G Benoit","year":"2008","unstructured":"Benoit, G., Boyd, S.: Finding the exact integrality gap for small travelling salesman problems. Math. Oper. Res. 33, 921\u2013931 (2008)","journal-title":"Math. Oper. Res."},{"key":"620_CR6","doi-asserted-by":"crossref","unstructured":"B\u00e9rczi, K., V\u00e9gh, L.A.: Restricted $$b$$ -matchings in degree-bounded graphs. In: Proceedings of the 14th Conference on Integer Programming and Combinatorial, Optimization, pp. 43\u201356 (2010)","DOI":"10.1007\/978-3-642-13036-6_4"},{"key":"620_CR7","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: 8\/7-approximation algorithm for 1,2-TSP. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 641\u2013648 (2006)","DOI":"10.1145\/1109557.1109627"},{"key":"620_CR8","unstructured":"Boyd, S., Iwata, S., Takazawa, K.: Finding 2-Factors Covering 3- and 4-Edge Cuts in Bridgeless Cubic Graphs. Manuscript, Kyoto University (2010)"},{"key":"620_CR9","unstructured":"Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: TSP on Cubic and Subcubic Graphs. Manuscript (2011). http:\/\/personal.vu.nl\/r.a.sitters\/papers\/GraphTsp.pdf"},{"key":"620_CR10","unstructured":"Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: TSP on cubic and subcubic graphs. Tech. Rep. arXiv (2011). http:\/\/arxiv.org\/abs\/1107.1052v1"},{"key":"620_CR11","doi-asserted-by":"crossref","unstructured":"Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: TSP on cubic and subcubic graphs. In: Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 6655, pp. 65\u201377 (2011)","DOI":"10.1007\/978-3-642-20807-2_6"},{"key":"620_CR12","unstructured":"Christofides, N.: Worst case analysis of a new heuristic for the traveling salesman problem. Tech. Rep. Report 388. Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh (1976)"},{"key":"620_CR13","doi-asserted-by":"crossref","unstructured":"Correa, J.R., Larr\u00e9, O., Soto, J.A.: TSP Tours in Cubic Graphs: beyond 4\/3. In: Proceedings of the 20th European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 7501, pp. 790\u2013801 (2011)","DOI":"10.1007\/978-3-642-33090-2_68"},{"key":"620_CR14","unstructured":"Csaba, B., Karpinski, M., Krysta, P.: Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 74\u201383 (2002)"},{"key":"620_CR15","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. Bureau Stand. B 69, 125\u2013130 (1965)","journal-title":"J. Res. Natl. Bureau Stand. B"},{"key":"620_CR16","unstructured":"Fotakis, D., Spirakis, P.: Graph properties that facilitate travelling. Electron. Colloquium Comput. Complex. 5(31) (1998)"},{"key":"620_CR17","unstructured":"Gabow, H.N.: Data structures for weighted matchings and nearest common ancestors with linking. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 434\u2013443 (1990)"},{"key":"620_CR18","doi-asserted-by":"crossref","unstructured":"Gamarnik, D., Lewenstein, M., Sviridenko, M.: An improved upper bound for the TSP in cubic 3-edge-connected graphs. OR Lett. 33, 467\u2013474 (2005)","DOI":"10.1016\/j.orl.2004.09.005"},{"key":"620_CR19","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M Garey","year":"1976","unstructured":"Garey, M., Johnson, D., Tarjan, R.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5, 704\u2013714 (1976)","journal-title":"SIAM J. Comput."},{"key":"620_CR20","first-page":"335","volume":"69","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X.: Worst-case comparison of valid inequalities for the TSP. Math. Program. 69, 335\u2013349 (1995)","journal-title":"Math. Program."},{"key":"620_CR21","doi-asserted-by":"crossref","unstructured":"Grigni, M., Koutsoupias, E., Papadimitriou, C.: An approximation scheme for planar graph TSP. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pp. 640\u2013645 (1995)","DOI":"10.1109\/SFCS.1995.492665"},{"key":"620_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)"},{"key":"620_CR23","unstructured":"Hartvigsen, D., Li, Y.: Maximum cardinality simple 2-matchings in subcubic graphs. SIAM J. Optim. 21(3), 1027\u20131045 (2011)"},{"key":"620_CR24","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/j.endm.2005.06.079","volume":"22","author":"T Kaiser","year":"2005","unstructured":"Kaiser, T., Kr\u00e1l, D., Norine, S.: Unions of perfect matchings in cubic graphs. Electron. Notes Discret. Math. 22, 341\u2013345 (2005)","journal-title":"Electron. Notes Discret. Math."},{"key":"620_CR25","volume-title":"The Traveling Salesman Problem-A Guided Tour of Combinatorial Optimization","author":"E Lawler","year":"1985","unstructured":"Lawler, E., Lenstra, J., Kan, A.R., Shmoys, D.: The Traveling Salesman Problem-A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)"},{"key":"620_CR26","doi-asserted-by":"crossref","unstructured":"M\u00f6mke, T., Svensson, O.: Approximating graphic TSP by matchings. Tech. Report arxiv (2011)","DOI":"10.1109\/FOCS.2011.56"},{"key":"620_CR27","doi-asserted-by":"crossref","unstructured":"M\u00f6mke, T., Svensson, O.: Approximating graphic TSP by matchings. In: Proceedings of the 52nd Symposium Foundations of Computer Science, pp. 560\u2013569 (2011)","DOI":"10.1109\/FOCS.2011.56"},{"key":"620_CR28","doi-asserted-by":"crossref","unstructured":"Mucha, M.: A 13\/9 -approximation for Graphic TSP. In: Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, pp. 30\u201341 (2012)","DOI":"10.1007\/s00224-012-9439-7"},{"key":"620_CR29","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0012-365X(81)90006-6","volume":"34","author":"D Naddef","year":"1981","unstructured":"Naddef, D., Pulleyblank, W.: Matchings in regular graphs. Discret. Math. 34, 283\u2013291 (1981)","journal-title":"Discret. Math."},{"key":"620_CR30","doi-asserted-by":"crossref","unstructured":"Oveis Gharan, S., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: Proceedings of the 52nd Symposium Foundations of Computer Science, pp. 550\u2013559 (2011)","DOI":"10.1109\/FOCS.2011.80"},{"key":"620_CR31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C Papadimitriou","year":"1993","unstructured":"Papadimitriou, C., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18, 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"key":"620_CR32","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 graphen. Acta Math. 15, 193\u2013220 (1891)","journal-title":"Acta Math."},{"key":"620_CR33","unstructured":"Seb\u00f6, A., Vygen, J.: Shorter tours by Nicer Ears: 7\/5-approximation for graphic TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. Tech. Rep. (2012). http:\/\/arxiv.org\/abs\/1201.1870"},{"key":"620_CR34","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0020-0190(90)90028-V","volume":"35","author":"D Shmoys","year":"1990","unstructured":"Shmoys, D., Williamson, D.: Analyzing the Held-Karp TSP bound: a monotonicity property with application. Inf. Process. Lett. 35, 281\u2013285 (1990)","journal-title":"Inf. Process. Lett."},{"key":"620_CR35","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BFb0120913","volume":"13","author":"L Wolsey","year":"1980","unstructured":"Wolsey, L.: Heuristic analysis, linear programming and branch and bound. Math. Program. Study 13, 121\u2013134 (1980)","journal-title":"Math. Program. Study"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-012-0620-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-012-0620-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-012-0620-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T03:05:37Z","timestamp":1745463937000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-012-0620-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,21]]},"references-count":35,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["620"],"URL":"https:\/\/doi.org\/10.1007\/s10107-012-0620-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12,21]]}}}