{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T07:18:19Z","timestamp":1767856699717,"version":"3.49.0"},"reference-count":35,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4788,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1993,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a new algorithm based upon network flows for finding all minimum\u2010size separating vertex sets in an undirected and unweighted graph. The sequential implementation of our algorithm runs in \u0398(<jats:italic>Mn<\/jats:italic> + <jats:italic>C<\/jats:italic>) = <jats:italic>O<\/jats:italic>(2<jats:italic><jats:sup>k<\/jats:sup>n<\/jats:italic><jats:sup>3<\/jats:sup>) time, where <jats:italic>M<\/jats:italic> is the number of minimum\u2010size separating vertex sets of the graph; <jats:italic>n<\/jats:italic>, the number of the vertices in the graph; <jats:italic>m<\/jats:italic>, the number of the edges in the graph; <jats:italic>k<\/jats:italic>, the connectivity of the graph, and <jats:italic>C<\/jats:italic> = <jats:italic>kn<\/jats:italic> min(<jats:italic>k<\/jats:italic>(<jats:italic>m<\/jats:italic> + <jats:italic>n<\/jats:italic>), <jats:italic>A<\/jats:italic>), where <jats:italic>A<\/jats:italic> is the complexity of the best maximum flow algorithm for unit networks. The parallel implementation runs either in <jats:italic>O<\/jats:italic>(<jats:italic>k<\/jats:italic> log <jats:italic>n<\/jats:italic>) deterministic time or in <jats:italic>O<\/jats:italic>(log<jats:sup>2<\/jats:sup> <jats:italic>n<\/jats:italic>) randomized time using \u0398(;<jats:italic>M<\/jats:italic><jats:sup>2<\/jats:sup><jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup> + <jats:italic>knN<\/jats:italic><jats:sup>\u03b1<\/jats:sup>) = <jats:italic>O<\/jats:italic>(4<jats:italic><jats:sup>k<\/jats:sup><\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>6<\/jats:sup>\/<jats:italic>k<\/jats:italic><jats:sup>2<\/jats:sup>)) processors on a PRAM, where <jats:italic>N<\/jats:italic><jats:sup>\u03b1<\/jats:sup> is the number of processors needed for parallel matrix multiplication in <jats:italic>O<\/jats:italic>(log <jats:italic>n<\/jats:italic>) time on PRAM. \u00a9 <jats:italic>1993 by John Wiley &amp; Sons, Inc.<\/jats:italic><\/jats:p>","DOI":"10.1002\/net.3230230604","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T16:17:58Z","timestamp":1178986678000},"page":"533-541","source":"Crossref","is-referenced-by-count":24,"title":["Finding all minimum\u2010size separating vertex sets in a graph"],"prefix":"10.1002","volume":"23","author":[{"given":"Arkady","family":"Kanevsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.27.4.823"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130210"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90046-1"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100404"},{"key":"e_1_2_1_6_2","first-page":"31","article-title":"The reliability polynomial","volume":"21","author":"Colbourn C. J.","year":"1986","journal-title":"ARS Combin."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0204034"},{"key":"e_1_2_1_8_2","volume-title":"Graph Algorithms","author":"Even S.","year":"1979"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0209016"},{"key":"e_1_2_1_11_2","series-title":"Technical Report ACT\u201077","volume-title":"On finding the vertex connectivity of graphs","author":"Girdkar M.","year":"1987"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90079-X"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"D. S.Hirshberg Parallel algorithms for transitive closure and connected components problems.Proceedings of the 8th Annual ACM Symposium on Theory of Computing New York(1976)55\u201357.","DOI":"10.1145\/800113.803631"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"J. E.HopcroftandR. E.Tarjan Dividing graph into triconnected components.SIAM J. Comput.(1973)135\u2013158.","DOI":"10.1137\/0202012"},{"key":"e_1_2_1_15_2","unstructured":"A.Kanevsky Compact representation of the separating k\u2010sets of a graph Technical Report ACT\u201088 Coordinated Science Laboratory University of Illinois Urbana Ill (January1988)."},{"key":"e_1_2_1_16_2","unstructured":"A.Kanevsky On the number of minimum size separating vertex sets in a graph and how to find all of them.Proceedings of the 1st ACM\u2010SIAM Symposium on Discrete Algorithms(1990)411\u2013421."},{"key":"e_1_2_1_17_2","first-page":"213","article-title":"A characterization of separating pairs and triplets in a graph","volume":"74","author":"Kanevsky A.","year":"1990","journal-title":"Congress. Numer."},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","unstructured":"A.KanevskyandV.Ramachandran Improved algorithms for graph four\u2010connectivity.Proceedings of the 28th IEEE Annual Symposium on Foundations of Computer Science Los Angeles(October1987)252\u2013259.","DOI":"10.1109\/SFCS.1987.33"},{"key":"e_1_2_1_19_2","doi-asserted-by":"crossref","unstructured":"N.Linial L.Lovasz andA.Wigderson A physical interpretation of graph connectivity and its algorithmic applications.Proceedings of the 27th IEEE Annual Symposium on Foundations of Computer Science(1986).","DOI":"10.1109\/SFCS.1986.3"},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","unstructured":"L.Lovasz Computing ears and branchings in parallel.Proceedings of the 26th IEEE Annual Symposium on Foundations of Computer Science(1985)464\u2013467.","DOI":"10.1109\/SFCS.1985.16"},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","unstructured":"Y.Maon B.Schieber andU.Vishkin Parallel ear decomposition search (EDS) andst\u2010numbering in graphs.VLSI Algorithms and ArchitecturesLecture Notes in Computer Science 227. Springer\u2010Verlag Berlin (1986)34\u201345.","DOI":"10.1007\/3-540-16766-8_4"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"e_1_2_1_23_2","unstructured":"G. L.MillerandV.Ramachandran Efficient Parallel Ear Decomposition with Applications. Unpublished (January1986)."},{"key":"e_1_2_1_24_2","doi-asserted-by":"crossref","unstructured":"G. L.MillerandV.Ramachandran A new graph tri\u2010connectivity algorithm and its parallelization.Proceedings of the 19th ACM Annual Symposium on Theory of Computing New York(1987)335\u2013344.","DOI":"10.1145\/28395.28431"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120902"},{"key":"e_1_2_1_27_2","unstructured":"J. S.ProvanandD. R.Shier.A paradigm for listing (s\u2010t)\u2010cuts in graphs. Technical Report UNC\/OR TR91\u20103 Department of Operation Research University of North Carolina at Chapel Hill (February1991)."},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592076"},{"key":"e_1_2_1_29_2","volume-title":"Handbook of Theoretical Computer Science","author":"Ramachandran V.","year":"1990"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0040371"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/0132031"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90008-6"},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265"},{"key":"e_1_2_1_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"e_1_2_1_36_2","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","article-title":"Non\u2010separable and planar graphs","volume":"34","author":"Whitney H.","year":"1932","journal-title":"Trans. Am. Math. Soc."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230230604","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230230604","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T13:44:40Z","timestamp":1698241480000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230230604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,9]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1993,9]]}},"alternative-id":["10.1002\/net.3230230604"],"URL":"https:\/\/doi.org\/10.1002\/net.3230230604","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,9]]}}}