Yao Qi, Raja Das, et al.
ISSTA 2009
Given a graph G = (V,E) with nonnegative weights x(e) for each edge e, a partition inequality is of the form x(δ(S1,...,Sp))≥ap+b. Here δ(S1,...,Sp) denotes the multicut defined by a partition S1,...,Sp of V. Partition inequalities arise as valid inequalities for optimization problems related to k-connectivity. We give a polynomial algorithm for the associated separation problem. This is based on an algorithm for finding the minimum of x(δ(S1,...,Sp))-p that reduces to minimizing a symmetric submodular function. This is handled with the recent algorithm of Queyranne. We also survey some applications of partition inequalities.
Yao Qi, Raja Das, et al.
ISSTA 2009
Sai Zeng, Angran Xiao, et al.
CAD Computer Aided Design
Thomas R. Puzak, A. Hartstein, et al.
CF 2007
Renu Tewari, Richard P. King, et al.
IS&T/SPIE Electronic Imaging 1996