摘要: We study the max cut problem in graphs not contractible toK5, and optimum perfect matchings planar graphs. prove that both problems can be formulated as polynomial size linear programs.
springer.com
sci-hub.se 参考文章(22)
B Rothschild, A Whinston, PURDUE UNIV LAFAYETTE IND KRANNERT GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATION, MULTICOMMODITY NETWORK FLOWS. ,(1969)
Alexander Schrijver, Theory of Linear and Integer Programming ,(1986)
G. Cornuéjols, D. Naddef, W. Pulleyblank, The traveling salesman problem in graphs with 3-edge cutsets Journal of the ACM. ,vol. 32, pp. 383- 410 ,(1985) , 10.1145/3149.3154
Francisco Barahona, Ali Ridha Mahjoub, Compositions of Graphs and Polyhedra II: Stable Sets SIAM Journal on Discrete Mathematics. ,vol. 7, pp. 359- 371 ,(1994) , 10.1137/S0895480190182678
Francisco Barahona, Reducing Matching to Polynomial Size Linear Programming Siam Journal on Optimization. ,vol. 3, pp. 688- 695 ,(1993) , 10.1137/0803035
P.D. Seymour, Matroids and Multicommodity Flows European Journal of Combinatorics. ,vol. 2, pp. 257- 290 ,(1981) , 10.1016/S0195-6698(81)80033-9
Francisco Barahona, Ali Ridha Mahjoub, Compositions of Graphs and Polyhedra III: Graphs with No W 4 Minor SIAM Journal on Discrete Mathematics. ,vol. 7, pp. 372- 389 ,(1994) , 10.1137/S089548019018268X
Mihalis Yannakakis, Expressing combinatorial optimization problems by linear programs symposium on the theory of computing. pp. 223- 228 ,(1988) , 10.1145/62212.62232
K. Wagner, Beweis einer Abschwächung der Hadwiger-Vermutung. Mathematische Annalen. ,vol. 153, pp. 139- 141 ,(1964) , 10.1007/BF01361181
Francisco Barahona, Ali Ridha Mahjoub, On the cut polytope Mathematical Programming. ,vol. 36, pp. 157- 173 ,(1986) , 10.1007/BF02592023