On the k-cut problem
Francisco Barahona
Operations Research Letters
Given a graph where increasing the weight of an edge has a nondecreasing convex piecewise linear cost, we study the problem of finding a minimum cost increase of the weights so that the value of all minimum spanning trees is equal to some target value. Frederickson and Solis-Oba gave an algorithm for the case when the costs are linear. We give a different derivation of their algorithm, and we slightly extend it to deal with convex piecewise linear costs. We formulate the problem as a combinatorial linear program and show how to produce primal and dual solutions. © 2008 Wiley Periodicals, Inc.
Francisco Barahona
Operations Research Letters
Mourad Baiou, Francisco Barahona
Networks
David Melville, Alan E. Rosenbluth, et al.
SPIE Advanced Lithography 2010
Rui S. Shibasaki, Mourad Baiou, et al.
ITOR