Computing the strength of a weighted graph G(V,E) is an interesting graph partitioning problem. It involves finding a cut set A in E that partitions the vertex set V in such a way that a strength function S(A)/k(A) is minimized, where S(A) is the sum of the weights of the edges in A and k(A) is the number of additional subsets partitioned by the cut set A with the constraint that k(A)>0. The problem was proposed by Gusfield in 1983; Cunningham solved it in 1985 using a polymatroid approach in O ( | V | 4 | E | ) time.
In this paper, Gusfield demonstrates that a parametric flow algorithm proposed by Goldberg and Tarjan can be used to solve the problem and reduce the complexity to O ( | V | 3 | E | ), which makes the approach more applicable to very large systems. Therefore, these results suggest further research on applications to system design as well as on the solutions to variations of the strength function.
