{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:15:58Z","timestamp":1781345758673,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642208065","type":"print"},{"value":"9783642208072","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-20807-2_6","type":"book-chapter","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T09:58:49Z","timestamp":1308391129000},"page":"65-77","source":"Crossref","is-referenced-by-count":14,"title":["TSP on Cubic and Subcubic Graphs"],"prefix":"10.1007","author":[{"given":"Sylvia","family":"Boyd","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ren\u00e9","family":"Sitters","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Suzanne","family":"van der Ster","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"6_CR1","unstructured":"Aggarwal, N., Garg, N., Gupta, S.: A 4\/3-approximation for TSP on cubic 3-edge-connected graphs (2011) (manuscript)"},{"key":"6_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. Journal of Information Processing\u00a03, 73\u201376 (1980)","journal-title":"Journal of Information Processing"},{"key":"6_CR3","unstructured":"Arora, S., Grigni, M., Karger, D., Klein, P., Woloszyn, A.: A polynomial-time approximation scheme for weighted planar graph TSP. In: Proc. of the 9th ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 33\u201341 (1998)"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1137\/S0895480102409619","volume":"17","author":"F. Barahona","year":"2004","unstructured":"Barahona, F.: Fractional packing of T-joins. SIAM Journal on Discrete Math.\u00a017, 661\u2013669 (2004)","journal-title":"SIAM Journal on Discrete Math."},{"key":"6_CR5","doi-asserted-by":"publisher","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. of Operations Research\u00a033, 921\u2013931 (2008)","journal-title":"Math. of Operations Research"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: 8\/7-approximation algorithm for 1,2-TSP. In: Proc. 17th ACM SIAM Symposium on Discrete Algorithms, pp. 641\u2013648 (2006)","DOI":"10.1145\/1109557.1109627"},{"key":"6_CR7","unstructured":"Boyd, S., Iwata, S., Takazawa, K.: Finding 2-Factors Covering 3- and 4-Edge Cuts in Bridgeless Cubic Graphs Kyoto University (2010) (manuscript)"},{"key":"6_CR8","unstructured":"Csaba, B., Karpinski, M., Krysta, P.: Approximability of dense and sparse instances of minimum 2-connectivity, tsp and path problems. In: Proc. 13th ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 74\u201383 (2002)"},{"key":"6_CR9","unstructured":"Christofides, N.: Worst case analysis of a new heuristic for the traveling salesman problem, Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh (1976)"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01582008","volume":"33","author":"G. Cornu\u00e9jols","year":"1985","unstructured":"Cornu\u00e9jols, G., Fonlupt, J., Naddef, D.: The traveling salesman on a graph and some related integer polyhedra. Math. Programming\u00a033, 1\u201327 (1985)","journal-title":"Math. Programming"},{"key":"6_CR11","doi-asserted-by":"publisher","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. of Res. National Bureau of Standards B\u00a069, 125\u2013130 (1965)","journal-title":"J. of Res. National Bureau of Standards B"},{"key":"6_CR12","first-page":"1","volume":"31","author":"D. Fotakis","year":"1998","unstructured":"Fotakis, D., Spirakis, P.: Graph properties that facilitate travelling. Electronic Colloquium on Computational Complexity\u00a031, 1\u201318 (1998)","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/BF01584085","volume":"1","author":"D. Fulkerson","year":"1971","unstructured":"Fulkerson, D.: Blocking and anti-blocking pairs of polyhedra. Math Programming\u00a01, 168\u2013194 (1971)","journal-title":"Math Programming"},{"key":"6_CR14","first-page":"467","volume":"33","author":"D. Gamarnik","year":"2005","unstructured":"Gamarnik, D., Lewenstein, M., Sviridenko, M.: An improved upper bound for the TSP in cubic 3-edge-connected graphs. OR Letters\u00a033, 467\u2013474 (2005)","journal-title":"OR Letters"},{"key":"6_CR15","doi-asserted-by":"publisher","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 Journal of Computing\u00a05, 704\u2013714 (1976)","journal-title":"SIAM Journal of Computing"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Gharan, S.O., Saberi, A., Singh, M.: A Randomized Rounding Approach to the Traveling Salesman Problem (2011) (manuscript)","DOI":"10.1109\/FOCS.2011.80"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Grigni, M., Koutsoupias, E., Papadimitriou, C.: An approximation scheme for planar graph TSP. In: Proc. 36th Annual Symposium on Foundations of Computer Science, pp. 640\u2013645 (1995)","DOI":"10.1109\/SFCS.1995.492665"},{"key":"6_CR18","unstructured":"Hartvigsen, D., Li, Y.: Maximum cardinality simple 2-matchings in subcubic graphs, University of Notre Dame (2009) (manuscript)"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/j.endm.2005.06.079","volume":"22","author":"T. Kaiser","year":"2005","unstructured":"Kaiser, T., Kr\u00e1l\u2019, D., Norine, S.: Unions of perfect matchings in cubic graphs. Electronic Notes in Discrete Math.\u00a022, 341\u2013345 (2005)","journal-title":"Electronic Notes in Discrete Math."},{"key":"6_CR20","volume-title":"The Traveling Salesman Problem\u2013A 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\u2013A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)"},{"key":"6_CR21","doi-asserted-by":"publisher","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. Discrete Math.\u00a034, 283\u2013291 (1981)","journal-title":"Discrete Math."},{"key":"6_CR22","doi-asserted-by":"publisher","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.\u00a018, 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"key":"6_CR23","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 Math.\u00a015, 193\u2013220 (1891)","journal-title":"Acta Math."},{"key":"6_CR24","doi-asserted-by":"publisher","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. Information Processing Letters\u00a035, 281\u2013285 (1990)","journal-title":"Information Processing Letters"},{"key":"6_CR25","doi-asserted-by":"publisher","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. Programming Study\u00a013, 121\u2013134 (1980)","journal-title":"Math. Programming Study"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatoral Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20807-2_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T20:16:06Z","timestamp":1560284166000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20807-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208065","9783642208072"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20807-2_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}