An efficient algorithm for minimum k-covers in weighted graphs

Consider an edge-weighted graph G = (V, L), and define a k-cover C as a subset of the edges L such that each vertex in V is incident to at least one edge of C, and |C| = k. Given G and k, the problem is to find a k-cover of minimum weight sum. This paper presents characterizations of minimum k-covers, and shows their weight to be convex with the parameter k. An efficient algorithm is presented which generates minimum k-covers continuously as the parameter k ranges over all feasible values, together with a proof of optimality. The computational order of this algorithm is found to be |V| {dot operator} |L|2. © 1975 The Mathematical Programming Society