The line index and minimum cut of weighted graphs

In this paper we discuss the line index and the minimum capacity, sum of the weights in a minimum cut, of weighted graphs, relationships between the line index and the minimum capacity, between the two kinds of minimum capacities, and between graphs with only negative weights and graphs with both positive weights and negative weights. We provide linear algorithms for both the line index and the minimum capacity of series-parallel graphs. We discuss simplifications in computing the line index and the minimum capacity of weighted graphs. We show that the generalization of algorithm of Orlova and Dorfman, and Hadlock to mixed graphs is just one step. We also discuss the k-approximation of the minimum capacity.