COMPUTING THE STRENGTH OF A GRAPH

The strength of a graph is a measure of its vulnerability, strictly generalizing the edge connectivity of a weighted graph. Cunningham [J. Assoc. Comput. Mach., 32 (1985), pp. 549-562] showed how to compute the strength of a graph in O(\V\4\E\) time, using ideas from polymatroids and network flow. In this paper, his polymatroid approach is modified, a modified version of the Goldberg-Tarjan network flow algorithm [J. Assoc. Comput. Mach., 4 (1988), pp. 136-146] is used. Then, using ideas developed by Gallo, Grigoriadis, and Tarjan [SIAM J. Comput., 18 (1989), pp. 30-55], and by Gusfield, Martel, and Fernandez-Baca in [SIAM J. Comput., 16 (1987), pp. 237-251], it is shown that the solution runs in O(\V\3\E\) time. Analogous speedups for sparse-case bounds are also obtainable.