The paper contains a comprehensive survey of classical and recent results about connectivity and network flow problems. Since it is very well structured and since the problems are very well motivated, the paper is suitable for experts as a work of reference and for non-experts as a useful tool to become quickly familiar with the topics. Besides pure existence problems, the author also considers algorithmic aspects whenever it makes sense. Basic results such as Ford-Fulkerson’s algorithm for constructing flows of maximal values of Menger’s theorem are discussed in a detailed manner including proofs while other ones (especially those with an extensive proof such as Halin’s and Mader’s results about minimal and critical graphs) are just quoted. The main topics of the paper are the following:
Paths and reachability (detailed discussion): depth-first-search and breadth-first-search, algorithms for finding paths of minimum cost (Bellman-Ford and Dijkstra), cost-functions with negative values, circuits of negative weight.
Circulations and flows (detailed discussion): graphs with lower and upper edge-capacities, max-flow min-cut theorem and augmenting-paths-method of Ford-Fulkerson, refinements of Dinits and Edmonds-Karp, arc-version of Menger’s theorem as a consequence of the max-flow min-cut theorem, algorithms for finding circulations and flows of minimum costs.
Trees and arborescences (detailed discussion): algorithms for finding spanning trees and arborescences of minimum costs (Boruvka-Kruskal and Dijkstra-Prim), edge-disjoint \(s\)-arborescences (Edmonds), covering the arc-set (edge-set) by branchings (forests) (Edmonds, Nash-Williams).
Higher connectivity: all versions of Menger’s theorem as a consequence of its arc-version, Whitney’s theorem, highly arc-connected orientations of highly edge-connected graphs, construction of all \(n\)-edge-connected graphs for fixed \(n\) (Lovász, Mader), construction of all 2-connected and all 3-connected graphs (Tutte), preserving connectivity by deleting the vertices or edges of circuits or paths (a comprehensive list of results), minimal and critical graphs (Halin, Mader).
Multicommodity flows and disjoint paths: algorithmic aspects, necessary and sufficient conditions for the existence of edge-disjoint or vertex-disjoint paths between distinguished pairs of vertices (cut-criterion, high connectivity, topological aspects), flows of maximal values between distinguished pairs of sources and sinks (a comprehensive list of results).
For the entire collection see [Zbl 0833.05001].