On the k-cut problem

Authors
Barahona, F
Citation
F. Barahona, On the k-cut problem, OPER RES L, 26(3), 2000, pp. 99-105
Citations number
16
Categorie Soggetti
Engineering Mathematics
Journal title
OPERATIONS RESEARCH LETTERS
ISSN journal
01676377 → ACNP
Volume
26
Issue
3
Year of publication
2000
Pages
99 - 105
Database
ISI
SICI code
0167-6377(200004)26:3<99:OTKP>2.0.ZU;2-9
Abstract
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.