{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:59:08Z","timestamp":1725559148686},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540261995"},{"type":"electronic","value":"9783540321026"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11496915_31","type":"book-chapter","created":{"date-parts":[[2010,7,14]],"date-time":"2010-07-14T12:40:39Z","timestamp":1279111239000},"page":"422-436","source":"Crossref","is-referenced-by-count":2,"title":["Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem"],"prefix":"10.1007","author":[{"given":"Prabhakar","family":"Gubbala","sequence":"first","affiliation":[]},{"given":"Balaji","family":"Raghavachari","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1137\/S0895480199362071","volume":"14","author":"J. Cheriyan","year":"2001","unstructured":"Cheriyan, J., Seb\u0151, A., Szigeti, Z.: Improving on the 1.5 approximation of a smallest 2-edge connected spanning subgraph. SIAM J. Discret. Math.\u00a014, 170\u2013180 (2001)","journal-title":"SIAM J. Discret. Math."},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"Cheriyan, J., Vempala, S., Vetta, A.: Approximation algorithms for minimum-cost k-connected subgraphs. In: Proc. of the 34th ACM Symposium on the Theory of Computing, STOC (2002)","DOI":"10.1145\/509907.509955"},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1137\/S009753979833920X","volume":"30","author":"J. Cheriyan","year":"2000","unstructured":"Cheriyan, J., Thurimella, R.: Approximating minimum-size k-connected spanning subgraphs via Matching. SIAM J. Comput.\u00a030, 528\u2013560 (2000)","journal-title":"SIAM J. Comput."},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1006\/jagm.1998.0931","volume":"28","author":"C.G. Fernandes","year":"1998","unstructured":"Fernandes, C.G.: A better approximation for the minimum k-edge-connected spanning subgraph problem. J. Algorithms\u00a028, 105\u2013124 (1998)","journal-title":"J. Algorithms"},{"issue":"1","key":"31_CR5","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/S0895480102405476","volume":"18","author":"H.N. Gabow","year":"2004","unstructured":"Gabow, H.N.: An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph. SIAM J. Disc. Math.\u00a018(1), 41\u201370 (2004)","journal-title":"SIAM J. Disc. Math."},{"key":"31_CR6","unstructured":"Gabow, H.N.: Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph. In: Proc.\u00a014th Annual ACM-SIAM Symp.\u00a0on Discret. Algorithms, SODA (2003)"},{"key":"31_CR7","unstructured":"Garg, N., Santosh, V., Singla, A.: Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques. In: Proc.\u00a04th Annual ACM-SIAM Symp.\u00a0on Discret. Algorithms (SODA), pp. 103\u2013111 (1993)"},{"key":"31_CR8","unstructured":"Hartvigsen, D.: Extensions of matching theory, Ph.D. Thesis, Carnegie-Mellon University (1984)"},{"key":"31_CR9","doi-asserted-by":"crossref","unstructured":"Hartvigsen, D.: The square-free 2-factor problem in bipartite graphs. In: Proc. of the 7th Integer Programming and Combinatorial Optimization Conference (IPCO), pp. 234\u2013241 (1999)","DOI":"10.1007\/3-540-48777-8_18"},{"key":"31_CR10","unstructured":"Jothi, R., Raghavachari, B., Varadarajan, S.: A 5\/4-approximation algorithm for minimum 2-edge-connectivity. In: Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 725\u2013734 (2003)"},{"key":"31_CR11","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1006\/jagm.1996.0052","volume":"21","author":"S. Khuller","year":"1996","unstructured":"Khuller, S., Raghavachari, B.: Improved approximation algorithms for uniform connectivity problems. J. Algorithms\u00a021, 433\u2013450 (1996)","journal-title":"J. Algorithms"},{"key":"31_CR12","doi-asserted-by":"crossref","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. Assoc. Comput. Mach.\u00a041, 214\u2013235 (1994)","journal-title":"J. Assoc. Comput. Mach."},{"key":"31_CR13","doi-asserted-by":"crossref","unstructured":"Krysta, P., Anil Kumar, V.S.: Approximation algorithms for minimum size 2-connectivity problems. In: Proc. 18th Intl. Symposium on Theoretical Aspects of Computer Science (STACS), pp. 431\u2013442 (2001)","DOI":"10.1007\/3-540-44693-1_38"},{"key":"31_CR14","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: Linear time algorithms for finding sparse k-connected spanning subgraph of a k-connected graph. Algorithmica\u00a07, 583\u2013596 (1992)","journal-title":"Algorithmica"},{"key":"31_CR15","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)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11496915_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T02:40:29Z","timestamp":1619491229000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11496915_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540261995","9783540321026"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/11496915_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}