{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T05:40:18Z","timestamp":1737006018805,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540678236"},{"type":"electronic","value":"9783540449294"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44929-9_14","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:20:53Z","timestamp":1178371253000},"page":"169-185","source":"Crossref","is-referenced-by-count":1,"title":["The (\u03c3 + 1)-Edge-Connectivity Augmentation Problem without Creating Multiple Edges of a Graph"],"prefix":"10.1007","author":[{"given":"Satoshi","family":"Taoka","sequence":"first","affiliation":[]},{"given":"Toshimasa","family":"Watanabe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,24]]},"reference":[{"key":"14_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft AND J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"14_CR2","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1137\/S0895480197318878","volume":"11","author":"J. Bang-Jensen","year":"1998","unstructured":"J. Bang-Jensen AND T. Jord\u00e1n, Edge-connectivity augmentation preserving simplicity, SIAM J. Discrete Math., 11 (1998), pp. 603\u2013623.","journal-title":"SIAM J. Discrete Math."},{"key":"14_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 (1976), pp. 653\u2013655.","journal-title":"SIAM J. Comput."},{"key":"14_CR4","unstructured":"S. Even, Graph Algorithms, Pitman, London, 1979."},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"25","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, 5 (1992), pp. 25\u201353.","journal-title":"SIAM J. Discrete Mathematics"},{"key":"14_CR6","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1109\/TCT.1970.1083185","volume":"17","author":"H. Frank","year":"1970","unstructured":"H. Frank AND W. Chou, Connectivity considerations in the design of survivable networks, IEEE Trans. Circuit Theory, CT-17 (1970), pp. 486\u2013490.","journal-title":"IEEE Trans. Circuit Theory"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"H. N. Gabow, Applications of a poset representation to edge connectivity and graph rigidity, in Proc. 32nd IEEE Symposium on Foundations of Computer Science, 1991, pp. 812\u2013821.","DOI":"10.1109\/SFCS.1991.185453"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"-, Effcient splitting off algorithms for graphs, in Proc. 26th ACM Symposium on Theory of Computing, 1994, pp. 696\u2013705.","DOI":"10.1145\/195058.195436"},{"key":"14_CR9","volume-title":"Integer Programming and Network Flows","author":"T. C. Hu","year":"1969","unstructured":"T. C. Hu, Integer Programming and Network Flows, Addison-Wesley, Reading, Mass, 1969."},{"key":"14_CR10","first-page":"1997","volume-title":"Tech. Rep. PP-","author":"T. Jord\u00e1n","year":"1997","unstructured":"T. Jord\u00e1n, Two NP-complete augmentation problems, Tech. Rep. PP-1997\u201308, Odense University, Denmark, march 1997. http:\/\/www.imada.ou.dk\/Research\/Preprints\/j-l.html ."},{"key":"14_CR11","unstructured":"A. V. Karzanov AND E. A. Timofeev, Effcient algorithm for ffnding all minimal edge cuts of a nonoriented graph, Cybernetics, (dy1986), pp. 156\u2013162. Translated from Kibernetika, 2 (1986), 8\u201312."},{"key":"14_CR12","unstructured":"H. Nagamochi AND T. Ibaraki, A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem, Tech. Rep. 94017, Kyoto University, 1994."},{"key":"14_CR13","doi-asserted-by":"publisher","first-page":"1139","DOI":"10.1137\/S0097539792234226","volume":"26","author":"D. Naor","year":"1997","unstructured":"D. Naor, D. Gusfield, AND C. Martel, A fast algorithm for optimally increasing the edge connectivity, SIAM J. Comput., 26 (1997), pp. 1139\u20131165.","journal-title":"SIAM J. Comput."},{"key":"14_CR14","first-page":"33","volume":"AL-335","author":"D. Takafuji","year":"1993","unstructured":"D. Takafuji, S. Taoka, AND T. Watanabe, Simplicity-preserving augmentation to 4-edge-connect a graph, IPSJ SIG Notes, AL-335 (1993), pp. 33\u201340.","journal-title":"IPSJ SIG Notes"},{"key":"14_CR15","unstructured":"S. Taoka, D. Takafuji, AND T. Watanabe, Simplicity-preserving augmentation of the edge-connectivity of a graph, Tech. Rep. of IEICE of Japan, COMP9373 (1994), pp. 49\u201356."},{"key":"14_CR16","first-page":"1","volume":"42-1","author":"S. Taoka","year":"1994","unstructured":"S. Taoka AND T. Watanabe, Effcient algorithms for the edge-connectivity augmentation problem of graphs without increasing edge-multiplicity, IPSJ SIG Notes, AL-42-1 (1994), pp. 1\u20138.","journal-title":"IPSJ SIG Notes"},{"key":"14_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/3-540-58325-4_184","volume-title":"(Proc. 5th International Symposium on Algorithms and Computation(ISAAC\u201994))","author":"S. Taoka","year":"1994","unstructured":"-, Minimum augmentation to k-edge-connect specified vertices of a graph, in Lecture Notes in Computer Science 834(D-Z du and X-S Zhang(Eds.): Algorithms and Computation, Springer-Verlag, Berlin, 1994, pp. 217\u2013225. (Proc. 5th International Symposium on Algorithms and Computation(ISAAC\u201994))."},{"key":"14_CR18","first-page":"17","volume":"AL-383","author":"S. Taoka","year":"1994","unstructured":"-, Smallest augmentation to k-edge-connect all specified vertices in a graph, IPSJ SIG Notes, AL-383 (1994), pp. 17\u201324.","journal-title":"IPSJ SIG Notes"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"R. E. Tarjan, Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, PA, 1983.","DOI":"10.1137\/1.9781611970265"},{"key":"14_CR20","volume-title":"Tec. Rep.ACT-76-UILU-ENG-87-2221","author":"T. Watanabe","year":"1987","unstructured":"T. Watanabe, An effcient way for edge-connectivity augmentation, Tec. Rep.ACT-76-UILU-ENG-87-2221, Coordinated Science Lab., University of Illinois at Urbana, Urbana, IL 61801, April 1987. Also presented at Eighteenth Southeastern International Conference on Combinatorics, Graph Theory, Computing, No. 15, Boca Raton, FL, U.S.A., February 1987."},{"key":"14_CR21","unstructured":"-, A simple improvement on edge-connectivity augmentation, Tech. Rep., IEICE of Japan, CAS87-203 (1987), pp. 43\u201348."},{"key":"14_CR22","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, J. Comput. System Sci., 35 (1987), pp. 96\u2013144.","journal-title":"J. Comput. System Sci."},{"key":"14_CR23","unstructured":"T. Watanabe AND M. Yamakado, A linear time algorithm for smallest augmentation to 3-edge-connect a graph, IEICE Trans. Fundamentals of Japan, E76-A (1993), pp. 518\u2013531."}],"container-title":["Lecture Notes in Computer Science","Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44929-9_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T02:15:03Z","timestamp":1736993703000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44929-9_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540678236","9783540449294"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-44929-9_14","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}