{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T19:11:39Z","timestamp":1775070699362,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,2,22]],"date-time":"2012-02-22T00:00:00Z","timestamp":1329868800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s10732-012-9194-6","type":"journal-article","created":{"date-parts":[[2012,2,21]],"date-time":"2012-02-21T19:46:14Z","timestamp":1329853574000},"page":"473-503","source":"Crossref","is-referenced-by-count":13,"title":["Experimental analysis of heuristics for the bottleneck traveling salesman problem"],"prefix":"10.1007","volume":"18","author":[{"given":"John","family":"LaRusic","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abraham P.","family":"Punnen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Aubanel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,2,22]]},"reference":[{"key":"9194_CR1","unstructured":"Applegate, D., Bixby, R., Chvtal, V., Cook, W., Mevenkamp, M.: Concorde TSP solver. Last updated Jan. 2005. http:\/\/www.tsp.gatech.edu\/concorde.html"},{"key":"9194_CR2","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1137\/S0097539797320281","volume":"29","author":"E.M. Arkin","year":"1999","unstructured":"Arkin, E.M., Chiang, Y., Mitchell, J.S.B., Skiena, S.S., Yang, T.: On the maximum scatter traveling salesman problem. SIAM J. Comput. 29, 515\u2013544 (1999)","journal-title":"SIAM J. Comput."},{"key":"9194_CR3","first-page":"207","volume-title":"The Travelling Salesman Problem and Its Variants","author":"S. Arora","year":"2002","unstructured":"Arora, S.: Approximation algorithms for geometric TSP. In: Gutin, G., Punnen, A.P. (eds.) The Travelling Salesman Problem and Its Variants, pp. 207\u2013222. Kluwer Academic, Secaucus (2002), Chap.\u00a05"},{"key":"9194_CR4","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1287\/opre.36.2.192","volume":"36","author":"M.O. Ball","year":"1988","unstructured":"Ball, M.O., Magazine, M.J.: Sequencing of insertions in printed circuit board assembly. Oper. Res. 36, 192\u2013201 (1988)","journal-title":"Oper. Res."},{"key":"9194_CR5","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1287\/opre.32.2.380","volume":"32","author":"G. Carpaneto","year":"1984","unstructured":"Carpaneto, G., Martello, S., Toth, P.: An algorithm for the bottleneck traveling salesman problem. Oper. Res. 32, 380\u2013389 (1984)","journal-title":"Oper. Res."},{"key":"9194_CR6","first-page":"119","volume":"143","author":"N.N. Doroshko","year":"1981","unstructured":"Doroshko, N.N., Sarvanov, V.I.: The minimax traveling salesman problem and Hamiltonian cycles in powers of graphs. Vestsi Akad. Navuk BSSR, Ser. Fiz.-Mat. Navuk 143, 119\u2013120 (1981) (Russian)","journal-title":"Vestsi Akad. Navuk BSSR, Ser. Fiz.-Mat. Navuk"},{"key":"9194_CR7","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/S0021-9800(70)80083-7","volume":"8","author":"J. Edmonds","year":"1970","unstructured":"Edmonds, J., Fulkerson, F.R.: Bottleneck estrema. J. Comb. Theory 8, 299\u2013306 (1970)","journal-title":"J. Comb. Theory"},{"key":"9194_CR8","first-page":"3","volume":"22","author":"E. Gabovic","year":"1971","unstructured":"Gabovic, E., Ciz, A., Jalas, A.: The bottleneck travelling salesman problem. Tr. Vy\u010disl. Centra Tartu. Gos. Univ. 22, 3\u201324 (1971) (Russian)","journal-title":"Tr. Vy\u010disl. Centra Tartu. Gos. Univ."},{"key":"9194_CR9","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/322077.322086","volume":"25","author":"R.S. Garfinkel","year":"1978","unstructured":"Garfinkel, R.S., Gilbert, K.C.: The bottleneck traveling salesman problem: algorithms and probabilistic analysis. J. Assoc. Comput. Mach. 25, 435\u2013448 (1978)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9194_CR10","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1287\/opre.12.5.655","volume":"12","author":"P.C. Gilmore","year":"1964","unstructured":"Gilmore, P.C., Gomory, R.E.: Sequencing a one state-variable machine: a solvable case of the traveling salesman problem. Oper. Res. 12, 655\u2013679 (1964)","journal-title":"Oper. Res."},{"key":"9194_CR11","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","volume":"12","author":"K. Helsgaun","year":"2000","unstructured":"Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 12, 106\u2013130 (2000)","journal-title":"Eur. J. Oper. Res."},{"key":"9194_CR12","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"D.S. Hochbaum","year":"1986","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A unified approach to approximation algorithms for bottleneck problems. J. Assoc. Comput. Mach. 33, 533\u2013550 (1986)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9194_CR13","unstructured":"Johnson, D.S., McGeoch, L.A.: Benchmark code instance generation codes. http:\/\/www.research.att.com\/~dsj\/chtsp\/download.html (2002a). Last updated May 2002"},{"key":"9194_CR14","first-page":"369","volume-title":"The Travelling Salesman Problem and Its Variants","author":"D.S. Johnson","year":"2002","unstructured":"Johnson, D.S., McGeoch, L.A.: Experimental analysis of heuristics for the STSP. In: Gutin, G., Punnen, A.P. (eds.) The Travelling Salesman Problem and Its Variants, pp. 369\u2013444. Kluwer Academic, Secaucus (2002b), Chap.\u00a09"},{"key":"9194_CR15","first-page":"445","volume-title":"The Travelling Salesman Problem and Its Variants","author":"D.S. Johnson","year":"2002","unstructured":"Johnson, D.S., Gutin, G., McGeoch, L.A., Yeo, A., Zhang, W., Zverovitch, A.: Experimental analysis of heuristics for the ATSP. In: Gutin, G., Punnen, A.P. (eds.) The Travelling Salesman Problem and Its Variants, pp. 445\u2013489. Kluwer Academic, Secaucus (2002), Chap.\u00a010"},{"key":"9194_CR16","first-page":"489","volume-title":"The Travelling Salesman Problem and Its Variants","author":"S. Kabadi","year":"2002","unstructured":"Kabadi, S.: Polynomially solvable cases of the TSP. In: Gutin, G., Punnen, A.P. (eds.) The Travelling Salesman Problem and Its Variants, pp. 489\u2013584. Kluwer Academic, Secaucus (2002), Chap.\u00a011,"},{"key":"9194_CR17","first-page":"697","volume-title":"The Travelling Salesman Problem and Its Variants","author":"S. Kabadi","year":"2002","unstructured":"Kabadi, S., Punnen, A.P.: The bottleneck TSP. In: Gutin, G., Punnen, A.P. (eds.) The Travelling Salesman Problem and Its Variants, pp. 697\u2013736. Kluwer Academic, Secaucus (2002), Chap.\u00a015"},{"key":"9194_CR18","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.jda.2008.11.007","volume":"7","author":"M.Y. Kao","year":"2009","unstructured":"Kao, M.Y., Sanghi, M.: An approximation algorithm for a bottleneck traveling salesman problem. J. Discrete Algorithms 7, 315\u2013326 (2009)","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"9194_CR19","first-page":"61","volume":"141","author":"P.S. Kljaus","year":"1975","unstructured":"Kljaus, P.S.: A special case of the bottleneck traveling salesman problem. Vesci Akad. Navuk BSSR, Ser. Fiz.-Mat. Navuk 141(1), 61\u201365 (1975) (Russian)","journal-title":"Vesci Akad. Navuk BSSR, Ser. Fiz.-Mat. Navuk"},{"key":"9194_CR20","volume-title":"Traveling Salesman Problem: A\u00a0Guided Tour of Combinatorial Optimization","year":"1985","unstructured":"Lawler, E.L., Lenstra, J.K., Rinooy Kan, A.H.G., Shmoys, D.B. (eds.): Traveling Salesman Problem: A\u00a0Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)"},{"key":"9194_CR21","first-page":"972","volume":"21","author":"S. Lin","year":"1973","unstructured":"Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling salesman problem. Oper. Res. 21, 972\u2013989 (1973)","journal-title":"Oper. Res."},{"key":"9194_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0190(96)00088-9","volume":"59","author":"G.S. Manku","year":"1996","unstructured":"Manku, G.S.: A linear time algorithm for the bottleneck biconnected spanning subgraph problem. Inf. Process. Lett. 59, 1\u20137 (1996)","journal-title":"Inf. Process. Lett."},{"key":"9194_CR23","first-page":"269","volume":"12","author":"R.G. Parker","year":"1982","unstructured":"Parker, R.G., Rardin, R.L.: Guaranteed performance heuristics for the bottleneck traveling salesperson problem. Oper. Res. Lett. 12, 269\u2013272 (1982)","journal-title":"Oper. Res. Lett."},{"key":"9194_CR24","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0020-0190(98)00094-5","volume":"67","author":"J.M. Philips","year":"1998","unstructured":"Philips, J.M., Punnen, A.P., Kabadi, S.N.: A linear time algorithm for the bottleneck traveling salesman problem on a Halin graph. Inf. Process. Lett. 67, 105\u2013110 (1998)","journal-title":"Inf. Process. Lett."},{"key":"9194_CR25","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0020-0190(94)00041-7","volume":"50","author":"A.P. Punnen","year":"1994","unstructured":"Punnen, A.P., Nair, K.P.K.: A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem. Inf. Process. Lett. 50, 283\u2013286 (1994)","journal-title":"Inf. Process. Lett."},{"key":"9194_CR26","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s12597-009-0018-x","volume":"46","author":"R. Ramakrishnan","year":"2009","unstructured":"Ramakrishnan, R., Sharma, P., Punnen, A.P.: An efficient heuristic algorithm for the bottleneck traveling salesman problem. Opsearch 46, 275\u2013288 (2009)","journal-title":"Opsearch"},{"key":"9194_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1057\/jors.1972.1","volume":"23","author":"S.S. Reddi","year":"1972","unstructured":"Reddi, S.S., Ramamoorthy, R.: On the flow-shop sequencing problem with no wait in process. Oper. Res. Q. 23, 1\u20139 (1972)","journal-title":"Oper. Res. Q."},{"key":"9194_CR28","first-page":"309","volume-title":"The Travelling Salesman Problem and Its Variants","author":"C. Rego","year":"2002","unstructured":"Rego, C., Glover, F.: Local search and metaheuristics. In: The Travelling Salesman Problem and Its Variants, pp. 309\u2013367. Kluwer Academic, Secaucus (2002), Chap.\u00a08"},{"key":"9194_CR29","unstructured":"Reinelt, G.: TSPLIB. http:\/\/www.iwr.uni-heidelberg.de\/groups\/comopt\/software\/TSPLIB95\/ (2008)"},{"key":"9194_CR30","first-page":"16","volume":"39","author":"V.I. Sarvanov","year":"1995","unstructured":"Sarvanov, V.I.: A minimax traveling salesman problem on a plane: complexity of an approximate solution. Dokl. Akad. Nauk Belarus 39, 16\u201319 (1995) (Russian)","journal-title":"Dokl. Akad. Nauk Belarus"},{"issue":"7","key":"9194_CR31","first-page":"1027","volume":"56","author":"S.I. Sergeev","year":"1995","unstructured":"Sergeev, S.I.: Algorithms for solving a minimax traveling salesman problem. I. An approach based on dynamic programming. Autom. Remote Control 56(7), 1027\u20131032 (1995), Part\u00a02","journal-title":"Autom. Remote Control"},{"issue":"8","key":"9194_CR32","first-page":"1155","volume":"56","author":"S.I. Sergeev","year":"1995","unstructured":"Sergeev, S.I., Chernyshenko, A.V.: Algorithms for solving a minimax traveling salesman problem. II. A\u00a0dual approach. Autom. Remote Control 56(8), 1155\u20131168 (1995), Part\u00a02","journal-title":"Autom. Remote Control"},{"key":"9194_CR33","unstructured":"The world TSP page. http:\/\/www.tsp.gatech.edu\/world\/countries.html (2009)"},{"key":"9194_CR34","first-page":"75","volume":"4","author":"E.A. Timofeev","year":"1979","unstructured":"Timofeev, E.A.: Minmax di-associated subgraphs and the bottleneck traveling salesman problem. Cybernetics 4, 75\u201379 (1979)","journal-title":"Cybernetics"},{"key":"9194_CR35","unstructured":"UNB Advanced Computational Research Laboratory. http:\/\/acrl.cs.unb.ca (2005)"},{"key":"9194_CR36","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1016\/S0167-6377(03)00050-6","volume":"31","author":"G.L. Vairaktarakis","year":"2003","unstructured":"Vairaktarakis, G.L.: On Gilmore-Gomory\u2019s open question for the bottleneck TSP. Oper. Res. Lett. 31, 483\u2013491 (2003)","journal-title":"Oper. Res. Lett."},{"key":"9194_CR37","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0166-218X(93)90152-E","volume":"47","author":"J.A.A. Veen van\u00a0der","year":"1993","unstructured":"van\u00a0der Veen, J.A.A.: An O(n) algorithm to solve the bottleneck traveling salesman problem restricted to ordered product matrices. Discrete Appl. Math. 47, 57\u201375 (1993)","journal-title":"Discrete Appl. Math."}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-012-9194-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10732-012-9194-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-012-9194-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T22:54:32Z","timestamp":1559256872000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10732-012-9194-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,22]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9194"],"URL":"https:\/\/doi.org\/10.1007\/s10732-012-9194-6","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,22]]}}}