Given a graph with nonnegative edge-weights, let f(k) be the value of an op
timal solution of the k-cut problem. We study f as a function of k. Let g b
e the convex envelope of f. We give a polynomial algorithm to compute g. In
particular, if f is convex, then it can be computed in polynomial time for
all k. We show some experiments in computing g. (C) 2000 Elsevier Science
B.V. All rights reserved.