{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:48:40Z","timestamp":1725853720242},"publisher-location":"New York, NY","reference-count":14,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_171","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T20:15:58Z","timestamp":1553112958000},"page":"872-875","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"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","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"issue":"2","key":"159_CR7268","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1137\/S009753979833920X","volume":"30","author":"J Cheriyan","year":"2000","unstructured":"Cheriyan J, Thurimella R (2000) Approximating minimum-size k-connected spanning subgraphs via matching. SIAM J Comput 30(2):528\u2013560","journal-title":"SIAM J Comput"},{"issue":"4","key":"159_CR7269","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 (2003) An approximation algorithm for the minimum-cost k-vertex connected subgraph. SIAM J Comput 32(4):1050\u20131055","journal-title":"SIAM J Comput"},{"key":"159_CR7270","volume-title":"Combinatorial optimization","author":"WJ Cook","year":"1998","unstructured":"Cook WJ, Cunningham WH, Pulleyblank WR, Schrijver A (1998) Combinatorial optimization. Wiley, New York"},{"key":"159_CR7271","unstructured":"Gabow HN (2003) Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph. In: SODA, pp 460\u2013 469"},{"issue":"1","key":"159_CR7272","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/S0895480102405476","volume":"18","author":"HN Gabow","year":"2004","unstructured":"Gabow HN (2004) An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph. SIAM J Discret Math 18(1):41\u201370","journal-title":"SIAM J Discret Math"},{"key":"159_CR7273","first-page":"103","volume-title":"Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques","author":"N Garg","year":"1993","unstructured":"Garg N, Vempala S, Singla A (1993) Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques. In: SODA, pp 103\u2013111"},{"key":"159_CR7274","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/11496915_31","volume-title":"IPCO","author":"P Gubbala","year":"2005","unstructured":"Gubbala P, Raghavachari B (2005) Approximation algorithms for the minimum cardinality two-connected spanning subgraph problem. In: J\u00fcnger M, Kaibel V (eds) IPCO, vol 3509, Lecture notes in computer science. Springer, Berlin, pp 422\u2013436"},{"key":"159_CR7275","doi-asserted-by":"crossref","unstructured":"Gubbala P, Raghavachari B (2007) A 4\/3-approximation algorithm for minimum 3-edge-connectivity. In: Proceedings of the workshop on algorithms and data structures (WADS) August 2007, Halifax, pp 39\u201351","DOI":"10.1007\/978-3-540-73951-7_5"},{"key":"159_CR7276","first-page":"725","volume-title":"A 5\/4-approximation algorithm for minimum 2-edge-connectivity","author":"R Jothi","year":"2003","unstructured":"Jothi R, Raghavachari B, Varadarajan S (2003) A 5\/4-approximation algorithm for minimum 2-edge-connectivity. In: SODA, pp 725\u2013734"},{"issue":"2","key":"159_CR7277","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 (1996) Improved approximation algorithms for uniform connectivity problems. J Algorithms 21(2):434\u2013450","journal-title":"J Algorithms"},{"issue":"2","key":"159_CR7278","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1145\/174652.174654","volume":"41","author":"S Khuller","year":"1994","unstructured":"Khuller S, Vishkin U (1994) Biconnectivity approximations and graph carvings. J ACM 41(2):214\u2013235","journal-title":"J ACM"},{"key":"159_CR7279","first-page":"431","volume-title":"STACS. Lecture notes in computer science","author":"P Krysta","year":"2001","unstructured":"Krysta P, Kumar VSA (2001) Approximation algorithms for minimum size 2-connectivity problems. In: Ferreira A, Reichel H (eds) STACS. Lecture notes in computer science, vol 2010. Springer, Berlin, pp 431\u2013442"},{"issue":"5\u20136","key":"159_CR7280","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H Nagamochi","year":"1992","unstructured":"Nagamochi H, Ibaraki T (1992) A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica 7(5\u20136):583\u2013596","journal-title":"Algorithmica"},{"key":"159_CR7281","first-page":"262","volume-title":"APPROX. Lecture notes in computer science","author":"S Vempala","year":"2000","unstructured":"Vempala S, Vetta A (2000) Factor 4\/3 approximations for minimum 2-connected subgraphs. In: Jansen K, Khuller S (eds) APPROX. Lecture notes in computer science, vol 1913. Springer, Berlin, pp 262\u2013273"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_171","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T21:39:44Z","timestamp":1553117984000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_171"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_171","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}