On the k-cut problem

On the k-cut problem

0.00 Avg rating—0 Votes
Article ID: iaor20052282
Country: Netherlands
Volume: 26
Issue: 3
Start Page Number: 99
End Page Number: 105
Publication Date: Mar 2000
Journal: Operations Research Letters
Authors:
Keywords: combinatorial analysis
Abstract:

Given a graph with nonnegative edge-weights, let f(k) be the value of an optimal solution of the k-cut problem. We study f as a function of k. Let g be 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.

Reviews

Required fields are marked *. Your email address will not be published.