Bottlenecks and Edge Connectivity in Unsymmetrical Networks

DOI10.1137/0208019MaRDI QIDQ3204982zbMATH OpenOpenAlexFDO

Authors 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 complexitydirected graphminimum cutedge 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)

Cited in

(6)

• Efficient algorithm for computing all low \(s\)-\(t\) edge connectivities in directed graphs
• Extracting maximal information about sets of minimum cuts
• An algorithm for finding all thek-components of a digraph
• A linear time algorithm for computing 3-edge-connected components in a multigraph
• Revisiting parametric multi-terminal problems: maximum flows, minimum cuts and cut-tree computations
• Strong linear orderings of a directed network

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3204982)