Computing Vertex Connectivity: New Bounds from Old Techniques

DOI10.1006/jagm.1999.1055zbMath0951.68108OpenAlexW2132877659MaRDI QIDQ4943077

Satish B. Rao, Harold N. Gabow, Monika R. Henzinger

Publication date: 22 June 2000

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://infoscience.epfl.ch/record/99361/files/HenzingerRG00.pdf

zbMATH Keywords

algorithmvertex connectivity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (17)

Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time ⋮ On Element-Connectivity Preserving Graph Simplification ⋮ On the robustness of a synchronized multi-robot system ⋮ Some recent progress and applications in graph minor theory ⋮ Separator-based data reduction for signed graph balancing ⋮ On shredders and vertex connectivity augmentation ⋮ Graph connectivity, partial words, and a theorem of Fine and Wilf ⋮ Finding densest \(k\)-connected subgraphs ⋮ Characterizing and recognizing 4-map graphs ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ Construction for bicritical graphs and \(k\)-extendable bipartite graphs ⋮ Minimum \(k\)-critical bipartite graphs ⋮ Cycle-connected mixed graphs and related problems ⋮ Cycle-connected mixed graphs and related problems ⋮ Dynamic programming for graphs on surfaces ⋮ Tree-core and tree-coritivity of graphs ⋮ Minimum cost source location problem with vertex-connectivity requirements in digraphs

This page was built for publication: Computing Vertex Connectivity: New Bounds from Old Techniques