On the determination of the strength of a graph

The problem of determining the strength of a graph has applications in the analysis of bottlenecks in communication networks and is also used for decomposition of large networks in heuristic combinatorial algorithms (for example; for the solution of VLSI layout problems). Cunningham proposed an elegant strictly polynomial algorithm for its solution, reducing it to the solution of mn problems on the maximal flow in a network. It is known that the latter has complexity or . This note proposes a simpler algorithm requiring the computation of not more than maximal flows in the networks for the solution of this problem.