{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:32:27Z","timestamp":1725489147854},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540002253"},{"type":"electronic","value":"9783540362067"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36206-1_7","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T03:23:08Z","timestamp":1187234588000},"page":"59-70","source":"Crossref","is-referenced-by-count":10,"title":["On the Hardness of Constructing Minimal 2-Connected Spanning Subgraphs in Complete Graphs 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":[[2002,12,16]]},"reference":[{"issue":"2","key":"7_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":"7_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 parametrized triangle inequalities. SIAM Journal on Discrete Mathematics 8 (1995), pp. 1\u201316.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi: Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties. Springer 1999.","DOI":"10.1007\/978-3-642-58412-1"},{"key":"7_CR4","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":"7_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":"7_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/3-540-46521-9_7","volume-title":"Theoretical Computer Science","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":"7_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1007\/3-540-46541-3_32","volume-title":"An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality (Extended Abstract)","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":"7_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":"7_CR9","unstructured":"A. Czumaj, A. Lingas: On approximability of the minimum-cost k-connected spanning subgraph problem. Proc. SODA\u201999, 1999, pp. 281\u2013290."},{"key":"7_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/3-540-45841-7_18","volume-title":"Approximations for ATSP with Parametrized Triangle Inequality","author":"L. S. Chandran","year":"2002","unstructured":"L. S. Chandran, L. S. Ram: Approximations for ATSP with Parametrized Triangle Inequality. Proc. STACS 2002, LNCS 2285, Springer 2002, pp. 227\u2013237."},{"key":"7_CR11","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":"Fixed-parameter tractability and completeness"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"R. G. Downey, M. R. Fellows: Parameterized Complexity. Springer 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"4","key":"7_CR13","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1137\/0205044","volume":"5","author":"K. P. Eswaran","year":"1976","unstructured":"K. P. Eswaran, R. E. Tarjan: Augmentation Problems. SIAM Journal on Computing 5(4), 1976, pp. 653\u2013665.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"7_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-edgeconnected spanning subgraph problem. J. Algorithms, 28(1) (1998), pp. 105\u2013124.","journal-title":"J. Algorithms"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(82)90059-7","volume":"19","author":"G. N. Frederickson","year":"1982","unstructured":"G. N. Frederickson, J. J\u00e1j\u00e1: On the relationship between the biconnectivity augmentation and traveling salesman problems. Theoretical Computer Science, 19 (1982), pp. 189\u2013201.","journal-title":"Theoretical Computer Science"},{"key":"7_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/3-540-45678-3_30","volume-title":"Polynomial time algorithms for edge-connectivity augmentation of Hamiltonian paths","author":"A. Galluccio","year":"2001","unstructured":"A. Galluccio, G. Proietti: Polynomial time algorithms for edge-connectivity augmentation of Hamiltonian paths. Proc. ISAAC\u201901, LNCS 2223, Springer 2001, pp. 345\u2013354."},{"key":"7_CR17","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":"7_CR18","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, A. Schrijver: Geometric Algorithms and Combinatorial Optimization. Springer 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1016\/S0927-0507(05)80127-6","volume":"7","author":"M. Gr\u00f6tschel","year":"1995","unstructured":"M. Gr\u00f6tschel, C.L. Monma, M. Stoer: Design of survivable networks. Handbooks in OR and MS, Vol. 7, Elsevier (1995), pp. 617\u2013672.","journal-title":"Handbooks in OR and MS"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d: Algorithmics for Hard Problems-Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer 2001.","DOI":"10.1007\/978-3-662-04616-6_6"},{"key":"7_CR21","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1007\/3-540-44693-1_38","volume-title":"Approximation algorithms for minimum size 2-connectivity problems","author":"P. Krysta","year":"2001","unstructured":"P. Krysta, V. S. A. Kumar: Approximation algorithms for minimum size 2-connectivity problems. Proc. STACS 2001, LNCS 2010, Springer 2001, pp. 431\u2013442."},{"key":"7_CR22","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1006\/jagm.1993.1010","volume":"14","author":"S. Khuller","year":"1993","unstructured":"S. Khuller, R. Thurimella: Approximation algorithms for graph augmentation. Journal of Algorithms 14 (1993), pp. 214\u2013225.","journal-title":"Journal of Algorithms"},{"key":"7_CR23","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":"7_CR24","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/3-540-48686-0_3","volume-title":"An approximation for finding a smallest 2-edgeconnected subgraph containing a specified spanning tree","author":"H. Nagamochi","year":"1999","unstructured":"H. Nagamochi, T. Ibaraki: An approximation for finding a smallest 2-edgeconnected subgraph containing a specified spanning tree. Proc. COCOON\u201999, LNCS 1627, Springer 1999, pp. 31\u201340."},{"key":"7_CR25","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":"7_CR26","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/3-540-44436-X_26","volume-title":"Factor 4\/3 approximations for minimum 2-connected subgraphs","author":"S. Vempala","year":"2000","unstructured":"S. Vempala, A. Vetta: Factor 4\/3 approximations for minimum 2-connected subgraphs. Proc. APPROX 2000, LNCS 1913, Springer 2000, pp. 262\u2013273."}],"container-title":["Lecture Notes in Computer Science","FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36206-1_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T16:18:45Z","timestamp":1683994725000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36206-1_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540002253","9783540362067"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-36206-1_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}