Bottlenecks and Edge Connectivity in Unsymmetrical Networks

DOI10.1137/0208019zbMath0415.90037OpenAlexW2007557148MaRDI QIDQ3204982

Claus Peter Schnorr

Publication date: 1979

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0208019

zbMATH Keywords

computational complexityminimum cutdirected graphedge connectivityGomory-Hu algorithmmaximum flow matrixmultiterminal network flow

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Related Items (6)

Efficient Algorithm for Computing All Low s-t Edge Connectivities in Directed Graphs ⋮ An algorithm for finding all thek-components of a digraph ⋮ Revisiting parametric multi-terminal problems: maximum flows, minimum cuts and cut-tree computations ⋮ A linear time algorithm for computing 3-edge-connected components in a multigraph ⋮ Strong linear orderings of a directed network ⋮ Extracting maximal information about sets of minimum cuts

This page was built for publication: Bottlenecks and Edge Connectivity in Unsymmetrical Networks