{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T08:31:56Z","timestamp":1769934716437,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540401766","type":"print"},{"value":"9783540448495","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-44849-7_24","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T06:26:17Z","timestamp":1186727177000},"page":"189-200","source":"Crossref","is-referenced-by-count":9,"title":["On k-Edge-Connectivity Problems with Sharpened Triangle Inequality"],"prefix":"10.1007","author":[{"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"first","affiliation":[]},{"given":"Dirk","family":"Bongartz","sequence":"additional","affiliation":[]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[]},{"given":"Sebastian","family":"Seibert","sequence":"additional","affiliation":[]},{"given":"Walter","family":"Unger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,5,13]]},"reference":[{"issue":"2","key":"24_CR1","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.1024","volume":"38","author":"T. Andreae","year":"2001","unstructured":"T. Andreae: On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality. Networks 38(2) (2001), pp. 59\u201367.","journal-title":"Networks"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0895480192240226","volume":"8","author":"T. Andreae","year":"1995","unstructured":"T. Andreae, H.-J. Bandelt: Performance guarantees for approximation algorithms depending on parameterized triangle inequalities. SIAM Journal on Discrete Mathematics 8 (1995), pp. 1\u201316.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"24_CR3","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0020-0190(99)00160-X","volume":"73","author":"M.A. Bender","year":"2000","unstructured":"M.A. Bender, C. Chekuri: Performance guarantees for the TSP with a parameterized triangle inequality. Information Processing Letters 73 (2000), pp. 17\u201321.","journal-title":"Information Processing Letters"},{"key":"24_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/3-540-36206-1_7","volume-title":"Proc. FSTTCS 2002","author":"H.-J. B\u00f6ckenhauer","year":"2002","unstructured":"H.-J. B\u00f6ckenhauer, D. Bongartz, J. Hromkovi\u010d, R. Klasing, G. Proietti, S. Seibert, W. Unger: On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality. Proc. FSTTCS 2002, LNCS 2556, Springer 2002, pp. 59\u201370."},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0020-0190(00)00089-2","volume":"75","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"H.-J. B\u00f6ckenhauer, J. Hromkovi\u010d, R. Klasing, S. Seibert, W. Unger: Approximation algorithms for the TSP with sharpened triangle inequality. Information Processing Letters 75, 2000, pp. 133\u2013138.","journal-title":"Information Processing Letters"},{"key":"24_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/3-540-46521-9_7","volume-title":"Proc. CIAC 2000","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"H.-J. B\u00f6ckenhauer, J. Hromkovi\u010d, R. Klasing, S. Seibert, W. Unger: Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem (Extended Abstract). Proc. CIAC 2000, LNCS 1767, Springer 2000, pp. 72\u201386. Full version in Theoretical Computer Science 285(1) (2002), pp. 3\u201324."},{"key":"24_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1007\/3-540-46541-3_32","volume-title":"Proc. STACS 2000","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"H.-J. B\u00f6ckenhauer, J. Hromkovi\u010d, R. Klasing, S. Seibert, W. Unger: An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality (Extended Abstract). Proc. STACS 2000, LNCS 1770, Springer 2000, pp. 382\u2013394."},{"key":"24_CR8","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1051\/ita:2000115","volume":"34","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"H.-J. B\u00f6ckenhauer, S. Seibert: Improved lower bounds on the approximability of the traveling salesman problem. RAIRO-Theoretical Informatics and Applications 34, 2000, pp. 213\u2013255.","journal-title":"RAIRO-Theoretical Informatics and Applications"},{"key":"24_CR9","unstructured":"A. Czumaj, A. Lingas: On approximability of the minimum-cost k-connected spanning subgraph problem. SODA\u201999, 1999, pp. 281\u2013290."},{"issue":"2","key":"24_CR10","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1137\/S009753979833920X","volume":"30","author":"J. Cheriyan","year":"2000","unstructured":"J. Cheriyan, R. Thurimella: Approximating minimum-size k-connected spanning subgraphs via matching. SIAM Journal on Computing 30(2): 528\u2013560 (2000), pp. 528\u2013560.","journal-title":"SIAM Journal on Computing"},{"key":"24_CR11","unstructured":"R. Diestel: Graph Theory. Second Edition, Springer 2000."},{"key":"24_CR12","first-page":"161","volume":"87","author":"R.G. Downey","year":"1992","unstructured":"R.G. Downey, M.R. Fellows: Fixed-parameter tractability and completeness. Congressus Numerantium 87 (1992), pp. 161\u2013187.","journal-title":"Congressus Numerantium"},{"key":"24_CR13","doi-asserted-by":"crossref","unstructured":"R.G. Downey, M.R. Fellows: Parameterized Complexity. Springer 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"1","key":"24_CR14","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1006\/jagm.1998.0931","volume":"28","author":"C.G. Fernandes","year":"1998","unstructured":"C.G. Fernandes: A better approximation ratio for the minimum size k-edge-connected spanning subgraph problem. J. Algorithms, 28(1) (1998), pp. 105\u2013124.","journal-title":"J. Algorithms"},{"key":"24_CR15","volume-title":"Computers and Intractability: A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey, D.S. Johnson: Computers and Intractability: A guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco, 1979."},{"key":"24_CR16","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d: Stabilityof approximation algorithms and the knapsack problem. In: J. Karhumaki, H. Maurer, G. Paun, G. Rozenberg (Eds.) Jewels are Forever, Springer 1999, pp. 238\u2013249.","DOI":"10.1007\/978-3-642-60207-8_21"},{"key":"24_CR17","unstructured":"J. Hromkovi\u010d: Algorithmics for Hard Problems \u2014 Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer 2001."},{"issue":"2","key":"24_CR18","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1006\/jagm.1996.0052","volume":"21","author":"S. Khuller","year":"1996","unstructured":"S. Khuller, B. Raghavachari: Improved approximation algorithms for uniform connectivity problems. J. Algorithms 21(2): (1996), pp. 434\u2013450.","journal-title":"J. Algorithms"},{"key":"24_CR19","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1145\/174652.174654","volume":"41","author":"S. Khuller","year":"1994","unstructured":"S. Khuller, U. Vishkin: Biconnectivity approximations and graph carvings. Journal of the ACM 41 (1994), pp. 214\u2013235.","journal-title":"Journal of the ACM"},{"key":"24_CR20","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jagm.1995.0800","volume":"22","author":"M. Penn","year":"1997","unstructured":"M. Penn, H. Shasha-Krupnik: Improved approximation algorithms for weighted 2-and 3-vertex connectivity augmentation. Journal of Algorithms 22 (1997), pp. 187\u2013196.","journal-title":"Journal of Algorithms"},{"key":"24_CR21","unstructured":"D. Weckauf: Experimental Analysis of Approximation Algorithms for the Traveling Sales-person Problem with Relaxed Triangle Inequality. Diploma thesis, RWTH Aachen 2002 (in German)."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44849-7_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T04:48:39Z","timestamp":1550724519000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44849-7_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540401766","9783540448495"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-44849-7_24","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2003]]}}}