Extended formulations for the A-cut problem
作者： Sunil Chopra , Jonathan H. Owen
DOI: 10.1007/BF02592096
关键词:
摘要: LetG=(V, E) be an undirected graph andA⊆V. We consider the problem of finding a minimum cost set edges whose deletion separates every pair nodes inA. two extended formulations using both node and edge variables. An variable formulation has previously been considered for this (Chopra Rao (1991), Cunningham (1991)). show that LP-relaxations are stronger than LP-relaxation (even with extra class valid inequalities added). This is interesting because, while can solved in polynomial time, cannot. also give one formulations. Computational results performed.
springer.com
sci-hub.se 参考文章(9)
W.R. Pulleyblank, Chapter V Polyhedral combinatorics Handbooks in Operations Research and Management Science. ,vol. 1, pp. 371- 446 ,(1989) , 10.1016/S0927-0507(89)01006-6
M. Grötschel, L. Lovász, A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization Combinatorica. ,vol. 1, pp. 169- 197 ,(1981) , 10.1007/BF02579273
Egon Balas, William Pulleyblank, The perfectly matchable subgraph polytope of a bipartite graph Networks. ,vol. 13, pp. 495- 516 ,(1983) , 10.1002/NET.3230130405
Manfred Padberg, Giovanni Rinaldi, A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems SIAM Review. ,vol. 33, pp. 60- 100 ,(1991) , 10.1137/1033004
Sunil Chopra, M. R. Rao, On the multiway cut polyhedron Networks. ,vol. 21, pp. 51- 89 ,(1991) , 10.1002/NET.3230210106
E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, M. Yannakakis, The complexity of multiway cuts (extended abstract) symposium on the theory of computing. pp. 241- 251 ,(1992) , 10.1145/129712.129736
Olivier Goldschmidt, Dorit S. Hochbaum, A Polynomial Algorithm for the k-cut Problem for Fixed k Mathematics of Operations Research. ,vol. 19, pp. 24- 37 ,(1994) , 10.1287/MOOR.19.1.24
William H. Cunningham, The Optimal Multiterminal Cut Problem. Reliability Of Computer And Communication Networks. pp. 105- 120 ,(1989)
W. R. Pulleyblank, Polyhedral combinatorics Optimization. pp. 371- 446 ,(1989)