{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:55:44Z","timestamp":1725558944855},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540245742"},{"type":"electronic","value":"9783540318330"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31833-0_16","type":"book-chapter","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T14:11:05Z","timestamp":1278079865000},"page":"181-196","source":"Crossref","is-referenced-by-count":0,"title":["A $\\frac{5}{4}$ -Approximation Algorithm for Biconnecting a Graph with a Given Hamiltonian Path"],"prefix":"10.1007","author":[{"given":"Davide","family":"Bil\u00f2","sequence":"first","affiliation":[]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/3-540-36206-1_7","volume-title":"FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science","author":"H.-J. B\u00f6chenhauer","year":"2002","unstructured":"B\u00f6chenhauer, H.-J., Bongartz, D., Hromkovi\u010d, J., Klasing, R., Proietti, G., Seibert, S., Unger, W.: On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality, Theoretical Computer Science, 326, 137\u2013153 (2003); A preliminary version appeared. In: Agrawal, M., Seth, A.K. (eds.) FSTTCS 2002. LNCS, vol.\u00a02556, pp. 59\u201370. Springer, Heidelberg (2002)"},{"key":"16_CR2","first-page":"281","volume-title":"Proc. of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999)","author":"A. Czumaj","year":"1999","unstructured":"Czumaj, A., Lingas, A.: On approximability of the minimum-cost k-connected spanning subgraph problem. In: Proc. of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), pp. 281\u2013290. ACM Press, New York (1999)"},{"key":"16_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/b100033","volume-title":"Graph theory","author":"R. Diestel","year":"2000","unstructured":"Diestel, R.: Graph theory. electronic edn. Springer, Heidelberg (2000)"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(82)90059-7","volume":"19","author":"G.N. Frederickson","year":"1982","unstructured":"Frederickson, G.N., J\u00e1j\u00e1, J.: On the relationship between the biconnectivity augmentation and traveling salesman problems. Theoretical Computer Science\u00a019, 189\u2013201 (1982)","journal-title":"Theoretical Computer Science"},{"key":"16_CR5","volume-title":"Computers and intractability: a guide to the theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-Completeness. W.H. Freeman and Company, New York (1979)"},{"key":"16_CR6","first-page":"103","volume-title":"Proc. of the 4th ACM-SIAM Symp. on Discrete Algorithms (SODA 1993)","author":"N. Garg","year":"1993","unstructured":"Garg, N., Santosh, V.S., Singla, A.: Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques. In: Proc. of the 4th ACM-SIAM Symp. on Discrete Algorithms (SODA 1993), pp. 103\u2013111. ACM Press, New York (1993)"},{"key":"16_CR7","first-page":"725","volume-title":"Proc. of the 14th ACM-SIAM Symp. on Discrete Algorithms (SODA 2003)","author":"R. Jothi","year":"2003","unstructured":"Jothi, R., Raghavachari, B., Varadarajan, S.: A 5\/4-approximation algorithm for minimum 2-edge-connectivity. In: Proc. of the 14th ACM-SIAM Symp. on Discrete Algorithms (SODA 2003), pp. 725\u2013734. ACM Press, New York (2003)"},{"key":"16_CR8","unstructured":"Jothi, R.: Personal communication (2004)"},{"key":"16_CR9","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"S. Khuller","year":"1996","unstructured":"Khuller, S.: Approximation algorithms for finding highly connected subgraphs. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, Boston (1996)"},{"issue":"2","key":"16_CR10","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1145\/174652.174654","volume":"41","author":"S. Khuller","year":"1994","unstructured":"Khuller, S., Vishkin, U.: Biconnectivity approximations and graph carvings. J. ACM\u00a041(2), 214\u2013235 (1994)","journal-title":"J. ACM"},{"key":"16_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-45753-4_17","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"G. Kortsarz","year":"2002","unstructured":"Kortsarz, G., Krauthgamer, R., Lee, J.R.: Hardness of approximation for vertex-connectivity network-design problems. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, pp. 185\u2013199. Springer, Heidelberg (2002)"},{"key":"16_CR12","first-page":"1","volume-title":"Proc. of the 8th ACM Symp. on Theory of Computing (STOC 1976)","author":"C.H. Papadimitriou","year":"1976","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Some complexity results for the Traveling Salesman Problem. In: Proc. of the 8th ACM Symp. on Theory of Computing (STOC 1976), pp. 1\u20139. ACM Press, New York (1976)"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/3-540-44436-X_26","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"S. Vempala","year":"2000","unstructured":"Vempala, S., Vetta, A.: Factor 4\/3 approximations for minimum 2-connected subgraphs. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol.\u00a01913, pp. 262\u2013273. Springer, Heidelberg (2000)"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","volume":"34","author":"H. Whitney","year":"1932","unstructured":"Whitney, H.: Nonseparable and planar graphs. Trans. Amer. Math. Soc.\u00a034, 339\u2013362 (1932)","journal-title":"Trans. Amer. Math. Soc."}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31833-0_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,2]],"date-time":"2021-05-02T23:41:24Z","timestamp":1619998884000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31833-0_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540245742","9783540318330"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31833-0_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}