{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T20:27:54Z","timestamp":1769977674843,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540412557","type":"print"},{"value":"9783540409960","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-40996-3_27","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:17:32Z","timestamp":1188350252000},"page":"313-325","source":"Crossref","is-referenced-by-count":8,"title":["A Near Optimal Algorithm for Vertex Connectivity Augmentation"],"prefix":"10.1007","author":[{"given":"Bill","family":"Jackson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tibor","family":"Jord\u00e1n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,1,29]]},"reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1002\/net.3230190112","volume":"19","author":"G. R. Cai","year":"1989","unstructured":"G. R. Cai and Y. G. Sun, The minimum augmentation of any graph to a k-edge-connected graph, Networks 19 (1989) 151\u2013172.","journal-title":"Networks"},{"key":"27_CR2","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1137\/0222013","volume":"22","author":"J. Cheriyan","year":"1993","unstructured":"J. Cheriyan, M. Y. Kao, and R. Thurimella, Scan-first search and sparse certificates: An improved parallel algorithm for k-vertex connectivity, SIAM J. Comput. 22 (1993), 157\u2013174.","journal-title":"SIAM J. Comput."},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1006\/jagm.1999.1040","volume":"33","author":"J. Cheriyan","year":"1999","unstructured":"J. Cheriyan and R. Thurimella, Fast algorithms for k-shredders and k-node connectivity augmentation, Journal of Algorithms 33 (1999), 15\u201350.","journal-title":"Journal of Algorithms"},{"issue":"4","key":"27_CR4","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1137\/0205044","volume":"5","author":"K. P. Eswaran","year":"1976","unstructured":"K. P. Eswaran and R. E. Tarjan, Augmentation problems, SIAM J. Computing, Vol. 5, No. 4, 653\u2013665, 1976.","journal-title":"SIAM J. Computing"},{"issue":"1","key":"27_CR5","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1137\/0405003","volume":"5","author":"A. Frank","year":"1992","unstructured":"A. Frank, Augmenting graphs to meet edge-connectivity requirements, SIAM J. Discrete Mathematics, Vol.5, No 1., 22\u201353, 1992.","journal-title":"SIAM J. Discrete Mathematics"},{"key":"27_CR6","unstructured":"A. Frank, Connectivity augmentation problems in network design, Mathematical Programming: State of the Art (J.R. Birge, K. G. Murty eds.), 34\u201363, 1994."},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jctb.1995.1044","volume":"65","author":"A. Frank","year":"1995","unstructured":"A. Frank and T. Jord\u00e1n, Minimal edge-coverings of pairs of sets, J. Combinatorial Theory, Ser. B. 65, 73\u2013110 (1995).","journal-title":"J. Combinatorial Theory, Ser. B."},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, C. L. Monma and M. Stoer, Design of survivable networks, in: Handbook in Operations Research and Management Science Vol. 7, Network Models (M. O. Ball, T. L. Magnanti, C. L. Monma and G. L. Nemhauser, eds.) North-Holland, Amsterdam, 617\u2013672, 1994.","DOI":"10.1016\/S0927-0507(05)80127-6"},{"key":"27_CR9","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1006\/jagm.2000.1077","volume":"35","author":"T.-S. Hsu","year":"2000","unstructured":"T-S. Hsu, On four-connecting a triconnected graph, Journal of Algorithms 35, 202\u2013234, 2000.","journal-title":"Journal of Algorithms"},{"key":"27_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/BFb0015432","volume-title":"Undirected vertex-connectivity structure and smallest four-vertex-connectivity augmentation","author":"T.-S. Hsu","year":"1995","unstructured":"T-S. Hsu, Undirected vertex-connectivity structure and smallest four-vertex-connectivity augmentation, Algorithms and computation (Proc. 6th ISAAC\u2019 95), Springer Lecture Notes in Computer Science 1004, 274\u2013283, 1995."},{"key":"27_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/BFb0009497","volume-title":"Optimal augmentation for bipartite componentwise biconnectivity in linear time","author":"T.-S. Hsu","year":"1996","unstructured":"T-S. Hsu and M-Y. Kao, Optimal augmentation for bipartite componentwise biconnectivity in linear time, Algorithms and Computation (Proc. ISAAC\u2019 96), Springer Lecture Notes in Computer Science 1178, 213\u2013222, 1996."},{"key":"27_CR12","series-title":"Lect Notes Comput Sci","first-page":"102","volume-title":"Augmenting edge and vertex connectivities simultaneously","author":"T. Ishii","year":"1997","unstructured":"T. Ishii and H. Nagamochi and T. Ibaraki, Augmenting edge and vertex connectivities simultaneously, Algorithms and computation (Proc. ISAAC\u2019 97), Springer Lecture Notes in Computer Science 1350, 102\u2013111, 1997."},{"key":"27_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/3-540-44985-X_26","volume-title":"On the minimum augmentation of an l-connected graph to a k-connected graph","author":"T. Ishii","year":"2000","unstructured":"T. Ishii and H. Nagamochi, On the minimum augmentation of an l-connected graph to a k-connected graph, Proc. SWAT 2000 (M.M. Halld\u00f3rsson ed.) Springer LNCS 1851, pp. 286\u2013299, 2000."},{"key":"27_CR14","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1006\/jctb.1995.1002","volume":"63","author":"T. Jord\u00e1n","year":"1995","unstructured":"T. Jord\u00e1n, On the optimal vertex-connectivity augmentation, J. Combinatorial Theory, Ser. B. 63, 8\u201320,1995.","journal-title":"J. Combinatorial Theory, Ser. B."},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1006\/jctb.1997.1786","volume":"71","author":"T. Jord\u00e1n","year":"1997","unstructured":"T. Jord\u00e1n, A note on the vertex-connectivity augmentation problem, J. Combinatorial Theory, Ser. B. 71, 294\u2013301, 1997.","journal-title":"J. Combinatorial Theory, Ser. B."},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF01304873","volume":"23","author":"W. Mader","year":"1972","unstructured":"W. Mader, Ecken vom Grad n in minimalen n-fach zusammenh\u00e4ngenden Graphen, Archive der Mathematik 23 (1972), 219\u2013224.","journal-title":"Archive der Mathematik"},{"key":"27_CR17","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1007\/BF01758778","volume":"7","author":"H. Nagamochi","year":"1992","unstructured":"H. Nagamochi and T. Ibaraki, A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph, Algorithmica 7 (1992), 538\u2013596.","journal-title":"Algorithmica"},{"key":"27_CR18","unstructured":"H. Nagamochi, Recent development of graph connectivity augmentation algorithms, IEICE Trans. Inf. and Syst., vol E83-D, no.3, March 2000."},{"issue":"1","key":"27_CR19","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0022-0000(87)90038-9","volume":"35","author":"T. Watanabe","year":"1987","unstructured":"T. Watanabe and A. Nakamura, Edge-connectivity augmentation problems, Computer and System Siences, Vol 35, No. 1, 96\u2013144, 1987.","journal-title":"Computer and System Siences"},{"issue":"1","key":"27_CR20","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0022-0000(93)90050-7","volume":"46","author":"T. Watanabe","year":"1993","unstructured":"T. Watanabe and A. Nakamura, A minimum 3-connectivity augmentation of agraph, J. Computer and System Sciences, Vol. 46, No.1, 91\u2013128, 1993.","journal-title":"J. Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-40996-3_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T17:26:00Z","timestamp":1556817960000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-40996-3_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540412557","9783540409960"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-40996-3_27","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}