Given a graph
G with nonnegative edge costs and an integer
k, we consider the problem of finding an edge subset
S of minimum total cost with respect to the constraint that
S covers exactly
k vertices of
G. An
O(
n
3) algorithm is presented where
n is the order of
G. It is based on the author's previous paper dealing with a similar problem asking
S to cover at least
k vertices.
graph - network - edge cover - polynomial algorithm