---
_id: '11683'
abstract:
- lang: eng
  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.
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Satish
  full_name: Rao, Satish
  last_name: Rao
- first_name: Harold N.
  full_name: Gabow, Harold N.
  last_name: Gabow
citation:
  ama: '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>'
  apa: 'Henzinger, M., 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>'
  chicago: 'Henzinger, Monika, 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>.'
  ieee: 'M. 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.'
  ista: 'Henzinger M, Rao S, Gabow HN. 2000. Computing vertex connectivity: New bounds
    from old techniques. Journal of Algorithms. 34(2), 222–250.'
  mla: 'Henzinger, Monika, 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>.'
  short: M. Henzinger, S. Rao, H.N. Gabow, Journal of Algorithms 34 (2000) 222–250.
date_created: 2022-07-28T08:56:10Z
date_published: 2000-02-01T00:00:00Z
date_updated: 2024-11-04T11:42:08Z
day: '01'
doi: 10.1006/jagm.1999.1055
extern: '1'
intvolume: '        34'
issue: '2'
keyword:
- Computational Theory and Mathematics
- Computational Mathematics
- Control and Optimization
language:
- iso: eng
month: '02'
oa_version: None
page: 222-250
publication: Journal of Algorithms
publication_identifier:
  issn:
  - 0196-6774
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Computing vertex connectivity: New bounds from old techniques'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2000'
...