{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T09:10:06Z","timestamp":1737537006200,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662792"},{"type":"electronic","value":"9783540484479"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48447-7_10","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T21:42:14Z","timestamp":1194990134000},"page":"80-85","source":"Crossref","is-referenced-by-count":12,"title":["Performance Guarantees for the TSP with a Parameterized Triangle Inequality"],"prefix":"10.1007","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[]},{"given":"Chandra","family":"Chekuri","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,7,18]]},"reference":[{"issue":"1","key":"10_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0895480192240226","volume":"8","author":"T. Andreae","year":"1995","unstructured":"T. Andreae and H.-S. Bandelt. Performance guarantees for approximation algorithms depending on parametrized triangle inequalities. SIAM Journal of Discrete Mathematics, 8(1):1\u201316, February 1995.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. In 37th IEEE Symposium on Foundations of Computer Science, pages 2\u201312, 1996.","DOI":"10.1109\/SFCS.1996.548458"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"S. Arora. Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In 38th IEEE Symposium on Foundations of Computer Science, pages 554\u2013563, 1997.","DOI":"10.1109\/SFCS.1997.646145"},{"key":"10_CR4","unstructured":"N. Christofides. Worst-case analysis of a new heuristic for the Traveling Salesman Problem. Technical Report 338, Graduate School of Industrial Administration, Carnegie Mellon University, 1976."},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"L. Engebretsen. An explicit lower bound for TSP with distances one and two. Report No. 46 of the Electronic Colloquium on Computational Complexity, 1998.","DOI":"10.1007\/3-540-49116-3_35"},{"issue":"3","key":"10_CR6","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1023\/A:1008023416823","volume":"30","author":"R. Fagin","year":"1998","unstructured":"R. Fagin and L. Stockmeyer. Relaxing the triangle inequality in pattern matching. International Journal of Computer Vision, 30(3):219\u2013231, 1998.","journal-title":"International Journal of Computer Vision"},{"key":"10_CR7","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0095-8956(74)90090-2","volume":"16","author":"H. Fleischner","year":"1974","unstructured":"H. Fleischner. On spanning subgraphs of a connected bridgeless graph and their application to DT graphs. Journal of Combinatorial Theory, 16:17\u201328, 1974.","journal-title":"Journal of Combinatorial Theory"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0095-8956(74)90091-4","volume":"16","author":"H. Fleischner","year":"1974","unstructured":"H. Fleischner. The square of every two-connected graph is Hamiltonian. Journal of Combinatorial Theory, 16:29\u201334, 1974.","journal-title":"Journal of Combinatorial Theory"},{"key":"10_CR9","first-page":"236","volume-title":"Approximation Algorithms for NP-hard Problems","author":"S. Khuller","year":"1997","unstructured":"S. Khuller. Approximation algorithms for finding highly connected subgraphs. In Approximation Algorithms for NP-hard Problems, pages 236\u2013265. PWS Publishing Company, Boston, 1997."},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1006\/jagm.1996.0052","volume":"21","author":"S. Khuller","year":"1996","unstructured":"S. Khuller and B. Raghavachari. Improved approximation algorithms for uniform connectivity problems. Journal of Algorithms, 21:434\u2013450, 1996.","journal-title":"Journal of Algorithms"},{"key":"10_CR11","unstructured":"H. T. Lau. Finding a Hamiltonian Cycle in the Square of a Block. PhD thesis, McGill University, February 1980."},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/BF01564847","volume":"92","author":"H. T. Lau","year":"1981","unstructured":"H. T. Lau. Finding EPS-graphs. Monatshefte f\u00fcr Mathematik, 92:37\u201340, 1981.","journal-title":"Monatshefte f\u00fcr Mathematik"},{"key":"10_CR13","volume-title":"The Traveling Salesman Problem","author":"E. L. Lawler","year":"1985","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. RinnooyKan, and D. B. Shmoys. The Traveling Salesman Problem. John Wiley, New York, 1985."},{"key":"10_CR14","unstructured":"J. S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: Part ii-a simple polynomial-time approximation scheme for geometric k-MST, TSP, and related problems. To appear in SIAM Journal of Computing."},{"key":"10_CR15","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1117\/12.143648","volume":"1908","author":"W. Niblack","year":"1993","unstructured":"W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, and P. Yanker. The QBIC project: querying images by content using color, texture, and shape. In Proceedings of SPIE Conference on Storage and Retrieval for Image and Video Databases, volume 1908, pages 173\u2013181, 1993.","journal-title":"Proceedings of SPIE Conference on Storage and Retrieval for Image and Video Databases"},{"issue":"1","key":"10_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C. H. Papadimitriou","year":"1993","unstructured":"C. H. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Mathematics of Operations Research, 18(1):1\u201316, February 1993.","journal-title":"Mathematics of Operations Research"},{"issue":"6","key":"10_CR17","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0167-6377(84)90077-4","volume":"2","author":"R. GaryParker","year":"1984","unstructured":"R. GaryParker and Ronald L. Rardin. Guaranteed performance heuristics for the bottleneck traveling salesman problem. Operations Research Letters, 2(6):269\u2013272, 1984.","journal-title":"Operations Research Letters"},{"key":"10_CR18","series-title":"Technical Report","volume-title":"Improved approximation algorithms for weighted 2 & 3 vertex connectivity augmentation problems","author":"M. Penn","year":"1995","unstructured":"M. Penn and H. Shasha-Krupnik. Improved approximation algorithms for weighted 2 & 3 vertex connectivity augmentation problems. Technical Report TR-95-IEM\/OR-1, Industrial Engineering and Management, Technion, Israel, May 1995."},{"key":"10_CR19","first-page":"137","volume":"412","author":"M. Sekanina","year":"1960","unstructured":"M. Sekanina. On an ordering of the set of vertices of a connected graph. Publication of the Faculty of Sciences of the University of Brno, 412:137\u2013142, 1960.","journal-title":"On an ordering of the set of vertices of a connected graph"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48447-7_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T08:29:21Z","timestamp":1737534561000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48447-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662792","9783540484479"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-48447-7_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}