Computing vertex connectivity: New bounds from old techniques Henzinger, Monika H ; https://orcid.org/0000-0002-5008-6530 Rao, Satish Gabow, Harold N. Computational Theory and Mathematics Computational Mathematics Control and Optimization 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. Elsevier 2000 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/11683 Henzinger M, 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> eng info:eu-repo/semantics/altIdentifier/doi/10.1006/jagm.1999.1055 info:eu-repo/semantics/altIdentifier/issn/0196-6774 info:eu-repo/semantics/closedAccess