{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:09Z","timestamp":1742617149525,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540562795"},{"type":"electronic","value":"9783540475019"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-56279-6_55","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:58:25Z","timestamp":1330253905000},"page":"31-40","source":"Crossref","is-referenced-by-count":4,"title":["The k-edge-connectivity augmentation problem of weighted graphs"],"prefix":"10.1007","author":[{"given":"Toshimasa","family":"Watanabe","sequence":"first","affiliation":[]},{"given":"Toshiya","family":"Mashima","sequence":"additional","affiliation":[]},{"given":"Satoshi","family":"Taoka","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1002\/net.3230090403","volume":"9","author":"P.M. Camerini","year":"1979","unstructured":"P.M.Camerini, L.Fratta and F.Maffioli, A note on finding optimum branchings, Networks, 9, 309\u2013312 (1979).","journal-title":"Networks"},{"key":"4_CR2","first-page":"1396","volume":"14","author":"Y-J Chu","year":"1965","unstructured":"Y-J Chu and T-H Liu, On the shortest arborescence of a directed graph, SCIENTIASINICA, 14, 1396\u20131400 (1965).","journal-title":"SCIENTIASINICA"},{"key":"4_CR3","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.Comput, 5, 653\u2013655 (1976).","journal-title":"SIAM J.Comput"},{"key":"4_CR4","volume-title":"Graph Algorithms","author":"S. Even","year":"1979","unstructured":"S.Even, Graph Algorithms, Pitman, London (1979)."},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"A.Frank, Augmenting graphs to meet edge connectivity requirements, Proc. 31st Annual IEEE Symposium on Foundations of Computer Science, 708\u2013718 (1990).","DOI":"10.1109\/FSCS.1990.89593"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1137\/0210019","volume":"10","author":"G.N. Fredericson","year":"1981","unstructured":"G.N.Fredericson and J.Ja\u2032ja\u2032, Approximation algorithms for several graph augmentation problems, SIAM J.Comput., 10, 270\u2013283 (1981).","journal-title":"SIAM J.Comput."},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"H.N.Gabow, Applications of a poset representation to edge connectivity and graph rigidity, Proc. 32nd IEEE Symp. Found. Comp. Sci., 812\u2013821 (1991).","DOI":"10.1109\/SFCS.1991.185453"},{"issue":"2","key":"4_CR8","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H.N. Gabow","year":"1986","unstructured":"H.N.Gabow, Z.Galil, T.Spencer and R.E.Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, 6(2), 109\u2013122 (1986).","journal-title":"Combinatorica"},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1145\/122413.122416","volume":"22","author":"Z. Galil","year":"1991","unstructured":"Z.Galil and G.F.Italiano, Reducing edge connectivity to vertex connectivity, SIGACT NEWS, 22, 57\u201361 (1991).","journal-title":"SIGACT NEWS"},{"key":"4_CR10","volume-title":"Computers and Intractability: a Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1978","unstructured":"M.R.Garey and D.S.Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness, Freeman, San Francisco (1978)."},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"J.E.Hopcroft and R.E.Tarjan, Dividing a graph into triconnected components, SIAM J. Comput., 2, 135\u2013158 (1973).","journal-title":"SIAM J. Comput."},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"A.V.Karzanov and E.A.Timofeev, Efficient algorithm for finding all minimal edge cuts of a nonoriented graph, Cybernetics, 156\u2013162, Translated from Kibernetika, No.2, pp.8\u201312 (March\u2013April, 1986).","DOI":"10.1007\/BF01074775"},{"key":"4_CR13","unstructured":"T.Mashima, S.Taoka and T.Watanabe, Approximation Algorithms for the k-Edge-Connectivity Augmentation Problem, IEICE of Japan, Tech. Reserch Rep., COMP92-24, 11\u201320 (1992)."},{"key":"4_CR14","first-page":"606","volume-title":"Tech. Rep. #91005","author":"H. Nagamochi","year":"1991","unstructured":"H.Nagamochi and T.Ibaraki, A linear time algorithm for computing 3-edge-connected components of a multigraph, Tech. Rep. #91005, Dept. of Applied Mathematics and Physics, Faculty of Engineering, Kyoto Univ., Kyoto Japan, 606 (1991)."},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"D.Naor, D.Gusfield and C.Martel, A fast algorithm for optimally increasing the edge-connectivity, Proc. 31st Annual IEEE Symposium on Foundations of Computer Science, 698\u2013707 (1990).","DOI":"10.1109\/FSCS.1990.89592"},{"key":"4_CR16","first-page":"410","volume":"E75-3","author":"S. Taoka","year":"1991","unstructured":"S.Taoka, T.Watanabe and K.Onaga, A linear time algorithm for computing all 3-edge-connected components of an multigraph, Trans. IEICE, E75-3, 410\u2013424 (1991).","journal-title":"Trans. IEICE"},{"key":"4_CR17","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/net.3230070103","volume":"7","author":"R.E. Tarjan","year":"1977","unstructured":"R.E.Tarjan, Finding optimum branchings, Networks, 7, 25\u201335 (1977).","journal-title":"Networks"},{"key":"4_CR18","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R.E. Tarjan","year":"1983","unstructured":"R.E.Tarjan, Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, PA (1983)."},{"key":"4_CR19","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/net.3230180104","volume":"18","author":"S. Ueno","year":"1988","unstructured":"S.Ueno, Y.Kajitani, and H.Wada, The minimum augmentation of trees to k-edge-connected graphs, Networks, 18, 19\u201325 (1988).","journal-title":"Networks"},{"key":"4_CR20","doi-asserted-by":"crossref","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, Journal of Computer and System Sciences, 35, 96\u2013144 (1987).","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"T.Watanabe, T.Narita and A.Nakamura, 3-Edge-connectivity augmentation problems, Proc. 1989 IEEE ISCAS, 335\u2013338 (1989).","DOI":"10.1109\/ISCAS.1989.100359"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"T.Watanabe, M.Yamakado and K.Onaga, A linear-time augmenting algorithm for 3-edge-connectivity augmentation problems, Proc. 1991 IEEE ISCAS, 1168\u20131171 (1991).","DOI":"10.1109\/ISCAS.1991.176575"},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"T.Watanabe, S.Taoka and T.Mashima, Approximation algorithms for the 3-edge-connectivity augmentation problem of graphs, IEEE Asia-Pacific Conference on Circuits and Systems 1992, to appear.","DOI":"10.1007\/3-540-56279-6_55"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56279-6_55.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:46:34Z","timestamp":1742593594000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56279-6_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540562795","9783540475019"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-56279-6_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}