[{"publication_identifier":{"issn":["0196-6774"]},"type":"journal_article","date_published":"2000-02-01T00:00:00Z","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"02","oa_version":"None","publication":"Journal of Algorithms","keyword":["Computational Theory and Mathematics","Computational Mathematics","Control and Optimization"],"language":[{"iso":"eng"}],"abstract":[{"text":"The vertex connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m edges is O(min{κ3 + n, κn}m); for an undirected graph the term m can be replaced by κn. A randomized algorithm finds κ with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(κ1nmlog(n2/m)) where κ1 ≤ m/n is the unweighted vertex connectivity or in expected time O(nmlog(n2/m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a generalization of the preflow-push algorithm of Hao and Orlin (1994, J. Algorithms17, 424–446) that computes edge connectivity.","lang":"eng"}],"day":"01","doi":"10.1006/jagm.1999.1055","citation":{"ista":"Henzinger MH, Rao S, Gabow HN. 2000. Computing vertex connectivity: New bounds from old techniques. Journal of Algorithms. 34(2), 222–250.","short":"M.H. Henzinger, S. Rao, H.N. Gabow, Journal of Algorithms 34 (2000) 222–250.","mla":"Henzinger, Monika H., et al. “Computing Vertex Connectivity: New Bounds from Old Techniques.” <i>Journal of Algorithms</i>, vol. 34, no. 2, Elsevier, 2000, pp. 222–50, doi:<a href=\"https://doi.org/10.1006/jagm.1999.1055\">10.1006/jagm.1999.1055</a>.","ieee":"M. H. Henzinger, S. Rao, and H. N. Gabow, “Computing vertex connectivity: New bounds from old techniques,” <i>Journal of Algorithms</i>, vol. 34, no. 2. Elsevier, pp. 222–250, 2000.","chicago":"Henzinger, Monika H, Satish Rao, and Harold N. Gabow. “Computing Vertex Connectivity: New Bounds from Old Techniques.” <i>Journal of Algorithms</i>. Elsevier, 2000. <a href=\"https://doi.org/10.1006/jagm.1999.1055\">https://doi.org/10.1006/jagm.1999.1055</a>.","ama":"Henzinger MH, Rao S, Gabow HN. Computing vertex connectivity: New bounds from old techniques. <i>Journal of Algorithms</i>. 2000;34(2):222-250. doi:<a href=\"https://doi.org/10.1006/jagm.1999.1055\">10.1006/jagm.1999.1055</a>","apa":"Henzinger, M. H., Rao, S., &#38; Gabow, H. N. (2000). Computing vertex connectivity: New bounds from old techniques. <i>Journal of Algorithms</i>. Elsevier. <a href=\"https://doi.org/10.1006/jagm.1999.1055\">https://doi.org/10.1006/jagm.1999.1055</a>"},"year":"2000","date_updated":"2022-09-12T09:06:48Z","extern":"1","volume":34,"intvolume":"        34","title":"Computing vertex connectivity: New bounds from old techniques","date_created":"2022-07-28T08:56:10Z","article_processing_charge":"No","publication_status":"published","issue":"2","author":[{"last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Rao","first_name":"Satish","full_name":"Rao, Satish"},{"last_name":"Gabow","first_name":"Harold N.","full_name":"Gabow, Harold N."}],"scopus_import":"1","_id":"11683","article_type":"original","publisher":"Elsevier","quality_controlled":"1","page":"222-250"}]