{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T18:32:05Z","timestamp":1743100325226,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":14,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_171","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:38:09Z","timestamp":1214505489000},"page":"371-373","source":"Crossref","is-referenced-by-count":3,"title":["Graph Connectivity"],"prefix":"10.1007","author":[{"given":"Samir","family":"Khuller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Balaji","family":"Raghavachari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"171_CR1_171","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\u2011connected spanning subgraphs via matching. SIAM J. Comput. 30(2), 528\u2013560 (2000)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"171_CR2_171","doi-asserted-by":"publisher","first-page":"1050","DOI":"10.1137\/S0097539701392287","volume":"32","author":"J. Cheriyan","year":"2003","unstructured":"Cheriyan, J., Vempala, S., Vetta, A.: An approximation algorithm for the minimum-cost k-vertex connected subgraph. SIAM J. Comput. 32(4), 1050\u20131055 (2003)","journal-title":"SIAM J. Comput."},{"key":"171_CR3_171","volume-title":"Combinatorial optimization","author":"W.J. Cook","year":"1998","unstructured":"Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial optimization. Wiley, New York (1998)"},{"key":"171_CR4_171","unstructured":"Gabow, H.N.: Better performance bounds for finding the smallest k-edge connected spanning subgraph of a\u00a0multigraph. In: SODA, 2003, pp. 460\u2013469"},{"issue":"1","key":"171_CR5_171","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\u00a0multigraph. SIAM J. Discret. Math. 18(1), 41\u201370 (2004)","journal-title":"SIAM J. Discret. Math."},{"key":"171_CR6_171","unstructured":"Garg, N., Vempala, S., Singla, A.: Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques. In: SODA, 1993, pp. 103\u2013111"},{"key":"171_CR7_171","first-page":"422","volume-title":"IPCO. Lecture Notes in Computer Science, vol. 3509","author":"P. Gubbala","year":"2005","unstructured":"Gubbala, P., Raghavachari, B.: Approximation algorithms for the minimum cardinality two\u2010connected spanning subgraph problem. In: J\u00fcnger, M., Kaibel, V. (eds.) IPCO. Lecture Notes in Computer Science, vol.\u00a03509, pp.\u00a0422\u2013436. Springer, Berlin (2005)"},{"key":"171_CR8_171","doi-asserted-by":"crossref","unstructured":"Gubbala, P., Raghavachari, B.: A\u00a04\/3\u2011approximation algorithm for minimum 3-edge\u2010connectivity. In: Proceedings of the Workshop on Algoriths and Data Structures (WADS) August 2007, pp. 39\u201351. Halifax (2007)","DOI":"10.1007\/978-3-540-73951-7_5"},{"key":"171_CR9_171","unstructured":"Jothi, R., Raghavachari, B., Varadarajan, S.: A\u00a05\/4\u2011approximation algorithm for minimum 2-edge\u2010connectivity. In: SODA, 2003, pp. 725\u2013734"},{"issue":"2","key":"171_CR10_171","doi-asserted-by":"publisher","first-page":"434","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 21(2), 434\u2013450 (1996)","journal-title":"J. Algorithms"},{"issue":"2","key":"171_CR11_171","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 41(2), 214\u2013235 (1994)","journal-title":"J. ACM"},{"key":"171_CR12_171","first-page":"431","volume-title":"STACS. Lecture Notes in Computer Science, vol. 2010","author":"P. Krysta","year":"2001","unstructured":"Krysta, P., Kumar, V.S.A.: Approximation algorithms for minimum size 2-connectivity problems. In: Ferreira, A., Reichel, H. (eds.) STACS. Lecture Notes in Computer Science, vol.\u00a02010, pp.\u00a0431\u2013442. Springer, Berlin (2001)"},{"issue":"5\u20136","key":"171_CR13_171","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: A\u00a0linear-time algorithm for finding a\u00a0sparse k-connected spanning subgraph of a\u00a0k-connected graph. Algorithmica 7(5\u20136), 583\u2013596 (1992)","journal-title":"Algorithmica"},{"key":"171_CR14_171","first-page":"262","volume-title":"APPROX. Lecture Notes in Computer Science, vol. 1913","author":"S. Vempala","year":"2000","unstructured":"Vempala, S., Vetta, A.: Factor 4\/3 approximations for minimum 2\u2011connected subgraphs. In: Jansen, K., Khuller, S. (eds.) APPROX. Lecture Notes in Computer Science, vol.\u00a01913, pp.\u00a0262\u2013273. Springer, Berlin (2000)"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_171","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T02:18:18Z","timestamp":1662171498000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_171"}},"subtitle":["1994; Khuller, Vishkin"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_171","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}