{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T19:28:12Z","timestamp":1742930892333,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642021572"},{"type":"electronic","value":"9783642021589"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-02158-9_16","type":"book-chapter","created":{"date-parts":[[2009,6,17]],"date-time":"2009-06-17T11:36:06Z","timestamp":1245238566000},"page":"175-187","source":"Crossref","is-referenced-by-count":8,"title":["Effective Tour Searching for TSP by Contraction of Pseudo Backbone Edges"],"prefix":"10.1007","author":[{"given":"Changxing","family":"Dong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerold","family":"J\u00e4ger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dirk","family":"Richter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Molitor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","volume-title":"The Traveling Salesman Problem. A Computational Study","author":"D.L. Applegate","year":"2006","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., Cook, W.J.: The Traveling Salesman Problem. A Computational Study. Princeton University Press, Princeton (2006)"},{"issue":"1","key":"16_CR2","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.orl.2008.09.006","volume":"37","author":"D.L. Applegate","year":"2009","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., Cook, W.J., Espinoza, D., Goycoolea, M., Helsgaun, K.: Certification of an optimal Tour through 85,900 cities. Oper. Res. Lett.\u00a037(1), 11\u201315 (2009)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"16_CR3","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/ijoc.15.3.233.16078","volume":"15","author":"W. Cook","year":"2003","unstructured":"Cook, W., Seymour, P.: Tour Merging via Branch-Decomposition. INFORMS J. Comput.\u00a015(3), 233\u2013248 (2003)","journal-title":"INFORMS J. Comput."},{"key":"16_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Ernst, C., Dong, C., J\u00e4ger, G., Molitor, P., Richter, D.: Finding Good Tours for Huge Euclidean TSP Instances by Iterative Backbone Contraction (submitted for Publication, 2009)","DOI":"10.1007\/978-3-642-14355-7_13"},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/978-3-540-71615-0_7","volume-title":"Evolutionary Computation in Combinatorial Optimization","author":"T. Fischer","year":"2007","unstructured":"Fischer, T., Merz, P.: Reducing the Size of Traveling Salesman Problem Instances by Fixing Edges. In: Cotta, C., van Hemert, J. (eds.) EvoCOP 2007. LNCS, vol.\u00a04446, pp. 72\u201383. Springer, Heidelberg (2007)"},{"key":"16_CR7","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/11775096_19","volume-title":"Algorithmic Aspects in Information and Management","author":"B. Goldengorin","year":"2006","unstructured":"Goldengorin, B., J\u00e4ger, G., Molitor, P.: Some Basics on Tolerances. In: Cheng, S.-W., Poon, C.K. (eds.) AAIM 2006. LNCS, vol.\u00a04041, pp. 194\u2013206. Springer, Heidelberg (2006)"},{"issue":"9","key":"16_CR9","doi-asserted-by":"publisher","first-page":"716","DOI":"10.3844\/jcssp.2006.716.734","volume":"2","author":"B. Goldengorin","year":"2006","unstructured":"Goldengorin, B., J\u00e4ger, G., Molitor, P.: Tolerances Applied in Combinatorial Optimization. J. Comput. Sci.\u00a02(9), 716\u2013734 (2006)","journal-title":"J. Comput. Sci."},{"issue":"1","key":"16_CR10","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News\u00a038(1), 31\u201345 (2007)","journal-title":"SIGACT News"},{"volume-title":"The Traveling Salesman Problem and Its Variations","year":"2002","key":"16_CR11","unstructured":"Gutin, G., Punnen, A.P. (eds.): The Traveling Salesman Problem and Its Variations. Kluwer, Dordrecht (2002)"},{"issue":"1","key":"16_CR12","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","volume":"126","author":"K. Helsgaun","year":"2000","unstructured":"Helsgaun, K.: An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic. European Journal Oper. Res.\u00a0126(1), 106\u2013130 (2000)","journal-title":"European Journal Oper. Res."},{"key":"16_CR13","unstructured":"Helsgaun, K.: An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic. Writings on Computer Science\u00a0109 (2007)"},{"key":"16_CR14","unstructured":"H\u00fcffner, F.: Algorithms and Experiments for Parameterized Approaches to Hard Graph Problems. PhD Thesis, Friedrich-Schiller-University Jena, Germany (2007)"},{"key":"16_CR15","unstructured":"Kilby, P., Slaney, J.K., Walsh, T.: The Backbone of the Travelling Salesperson. In: Kaelbling, L.P., Saffiotti, A. (eds.) Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005), pp. 175\u2013180 (2005)"},{"volume-title":"The Traveling Salesman Problem - A Guided Tour of Combinatorial Optimization","year":"1985","key":"16_CR16","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.): The Traveling Salesman Problem - A Guided Tour of Combinatorial Optimization. John Wiley & Sons, Chicester (1985)"},{"key":"16_CR17","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S. Lin","year":"1973","unstructured":"Lin, S., Kernighan, B.W.: An Effective Heuristic Algorithm for the Traveling Salesman Problem. Oper. Res.\u00a021, 498\u2013516 (1973)","journal-title":"Oper. Res."},{"issue":"4","key":"16_CR18","doi-asserted-by":"publisher","first-page":"4667","DOI":"10.1103\/PhysRevE.59.4667","volume":"59","author":"A. M\u00f6bius","year":"1999","unstructured":"M\u00f6bius, A., Freisleben, B., Merz, P., Schreiber, M.: Combinatorial Optimization by Iterative Partial Transcription. Phys. Rev. E\u00a059(4), 4667\u20134674 (1999)","journal-title":"Phys. Rev. E"},{"key":"16_CR19","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R. Monasson","year":"1998","unstructured":"Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyanski, L.: Determining Computational Complexity for Characteristic Phase Transitions. Nature\u00a0400, 133\u2013137 (1998)","journal-title":"Nature"},{"key":"16_CR20","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Tractability","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Tractability. Oxford University Press, Oxford (2006)"},{"key":"16_CR21","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G. Reinelt","year":"1991","unstructured":"Reinelt, G.: TSPLIB \u2013 a Traveling Salesman Problem Library. ORSA J.\u00a0Comput.\u00a03, 376\u2013384 (1991)","journal-title":"ORSA J.\u00a0Comput."},{"key":"16_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/978-3-540-72845-0_30","volume-title":"Experimental Algorithms","author":"C.C. Ribeiro","year":"2007","unstructured":"Ribeiro, C.C., Toso, R.F.: Experimental Analysis of Algorithms for Updating Minimum Spanning Trees on Graphs Subject to Changes on Edge Weights. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol.\u00a04525, pp. 393\u2013405. Springer, Heidelberg (2007)"},{"key":"16_CR23","unstructured":"Richter, D.: Toleranzen in Helsgauns Lin-Kernighan-Heuristik f\u00fcr das TSP. Diploma Thesis, Martin-Luther-University Halle-Wittenberg, Germany (2006)"},{"key":"16_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-540-77294-1_10","volume-title":"Combinatorial and Algorithmic Aspects of Networking","author":"D. Richter","year":"2007","unstructured":"Richter, D., Goldengorin, B., J\u00e4ger, G., Molitor, P.: Improving the Efficiency of Helsgaun\u2019s Lin-Kernighan Heuristic for the Symmetric TSP. In: Janssen, J., Pra\u0142at, P. (eds.) CAAN 2007. LNCS, vol.\u00a04852, pp. 99\u2013111. Springer, Heidelberg (2007)"},{"key":"16_CR25","unstructured":"Slaney, J.K., Walsh, T.: The Backbones in Optimization and Approximation. In: Nebel, B. (ed.) Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI 2001), pp. 254\u2013259 (2001)"},{"key":"16_CR26","unstructured":"Zhang, W., Looks, M.: A Novel Local Search Algorithm for the Traveling Salesman Problem that Exploits Backbones. In: Kaelbling, L.P., Saffiotti, A. (eds.) Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005), pp. 343\u2013350 (2005)"},{"key":"16_CR27","unstructured":"DIMACS Implementation Challenge: \n                  \n                    http:\/\/www.research.att.com\/~dsj\/chtsp\/"},{"key":"16_CR28","unstructured":"TSPLIB: \n                  \n                    http:\/\/elib.zib.de\/pub\/mp-testdata\/tsp\/tsplib\/tsplib.html"},{"key":"16_CR29","unstructured":"TSP Homepage, \n                  \n                    http:\/\/www.tsp.gatech.edu\/"},{"key":"16_CR30","unstructured":"National Instances from the TSP Homepage, \n                  \n                    http:\/\/www.tsp.gatech.edu\/world\/summary.html"},{"key":"16_CR31","unstructured":"VLSI Instances from the TSP Homepage, \n                  \n                    http:\/\/www.tsp.gatech.edu\/vlsi\/summary.html"},{"key":"16_CR32","unstructured":"World TSP from the TSP Homepage, \n                  \n                    http:\/\/www.tsp.gatech.edu\/world\/"},{"key":"16_CR33","unstructured":"Source Code of [1] (Concorde), \n                  \n                    http:\/\/www.tsp.gatech.edu\/concorde\/index.html"},{"key":"16_CR34","unstructured":"Source Code of [12] (LKH), \n                  \n                    http:\/\/www.akira.ruc.dk\/~keld\/research\/LKH\/"},{"key":"16_CR35","unstructured":"Additional Information about Experiments of this Paper, \n                  \n                    http:\/\/www.informatik.uni-halle.de\/ti\/forschung\/toleranzen\/kantenkontraktion"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02158-9_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T11:59:04Z","timestamp":1558267144000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02158-9_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642021572","9783642021589"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02158-9_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}