Paul J. Steinhardt, P. Chaudhari
Journal of Computational Physics
Paper
On the k-cut problem
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.
Related
R.B. Morris, Y. Tsuji, et al.
International Journal for Numerical Methods in Engineering
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences