{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T03:14:46Z","timestamp":1787368486029,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1993,10]]},"abstract":"<jats:p>The problem of finding a minimum number of edges whose addition biconnects an undirected graph is considered. This problem has been studied by several other researchers, two of whom presented a linear-time algorithm for this problem in an earlier volume of this journal. However, that algorithm contains an error that is exposed in this paper. A corrected linear-time algorithm for this problem, as well as a new efficient parallel algorithm, are presented. The parallel algorithm runs in $O(\\log ^2 n)$ time with a linear number of processors on an EREW PRAM, where n is the number of vertices in the input graph.<\/jats:p>","DOI":"10.1137\/0222056","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:38:56Z","timestamp":1109227136000},"page":"889-912","source":"Crossref","is-referenced-by-count":44,"title":["Finding a Smallest Augmentation to Biconnect a Graph"],"prefix":"10.1137","volume":"22","author":[{"given":"Tsan-Sheng","family":"Hsu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vijaya","family":"Ramachandran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230190112"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"R. Cole, U. Vishkin,  Approximate and exact parallel scheduling with applications to list, tree and graph problems,  Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC,  1986,  478\u2013491","DOI":"10.1109\/SFCS.1986.10"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0205044"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89593"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1970.1083185"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0210019"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0216041"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90062-9"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"T.S. Hsu, V. Ramachandran,  A linear time algorithm for triconneetivity augmentation,  Proc. 32th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC,  1991,  548\u2013559","DOI":"10.1109\/SFCS.1991.185418"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1986.4335542"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230160207"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89592"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90131-4"},{"key":"R17","first-page":"275","volume-title":"Synthesis of Parallel Algorithms","author":"Ramachandran V.","year":"1993"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0206003"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0040379"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90038-7"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1969.1083004"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180104"},{"key":"R25","unstructured":"T. Watanabe,  An efficient way for edge-connectivity augmentation, Tech. Report, ACT 76-UILU-ENG-87-2221, Coordinated Science Laboratory, University of Illinois, Urbana, IL,  1987"},{"key":"R26","unstructured":"T. Watanabe, A. Nakamura,  On a smallest augmentation to triconnect a graph, Tech. Report, C-18, Department of Applied Mathematics, Faculty of Engineering, Hiroshima University, Higashi-Hiroshima, Japan,  1983, revised 1987"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(87)90038-9"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"T. Watanabe, A. Nakamura,  3-connectivity augmentation problems,  Proc.1988 IEEE International Symposium on Circuits and Systems, Institute of Electrical and Electronics Engineers, New York,  1988,  1847\u20131850 0689.05036","DOI":"10.1109\/ISCAS.1988.15296"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"T. Watanabe, T. Narita, A. Nakamura,  3-edge-connectivity augmentation problems,  Proc. 1989 IEEE International Symposium on Circuits and Systems, Institute of Electrical and Electronics Engineers, New York,  1989,  335\u2013338","DOI":"10.1109\/ISCAS.1989.100359"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0222056","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:49:44Z","timestamp":1787338184000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0222056"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,10]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1993,10]]}},"alternative-id":["10.1137\/0222056"],"URL":"https:\/\/doi.org\/10.1137\/0222056","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,10]]}}}