@article{11683,
  abstract     = {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.},
  author       = {Henzinger, Monika H and Rao, Satish and Gabow, Harold N.},
  issn         = {0196-6774},
  journal      = {Journal of Algorithms},
  keywords     = {Computational Theory and Mathematics, Computational Mathematics, Control and Optimization},
  number       = {2},
  pages        = {222--250},
  publisher    = {Elsevier},
  title        = {{Computing vertex connectivity: New bounds from old techniques}},
  doi          = {10.1006/jagm.1999.1055},
  volume       = {34},
  year         = {2000},
}