×

zbMATH — the first resource for mathematics

The max-cut problem on graphs not contractible to \(K_ 5\). (English) Zbl 0525.90094

MSC:
90C35 Programming involving graphs or networks
90C10 Integer programming
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Araoz, J.; Cunningham, W.; Edmonds, J.; Green-Krotki, J., Reductions to 1-matching polyhedra, () · Zbl 0525.90068
[2] Bachem, A.; Grätschel, M., New aspects of polyhedral theory, (), 51-106
[3] Barahona, F., On the complexity of MAX cut, ()
[4] Barahona, F., Balancing signed toroidal graphs in polynomial time, (1982), Depto. de Matematicas, Universidad de Chile Santiago, Chile
[5] Barahona, F., On the computational complexity of Ising spin Glass models, J. phys. A, 15, 3241-3253, (1982)
[6] Barahona, F.; Grötschel, M.; Mahjoub, A.R., Facets of the bipartite subgraph polytope, () · Zbl 0578.05056
[7] Cornuéjols, G.; Naddef, D.; Pulleyblank, W., The travelling salesman problem in graphs with 3-edge cutsets, () · Zbl 0634.90089
[8] Edmonds, J., Maximum matching and a polyhedron of 0-1 vertices, J. res. nat. bur. standards sect. B, 69, 125-130, (1965) · Zbl 0141.21802
[9] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[10] Grötschel, M.; Pulleyblank, W.R., Weakly bipartite graphs and the MAX-cut problem, Oper. res. lett., 1, 23-27, (1981) · Zbl 0494.90078
[11] Grötschel, M.; Nemhauser, G.L., A polynomial algorithm for the MAX-cut problem on graphs without long odd cycles, () · Zbl 0532.90074
[12] Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid methid and its consequences in combinatorial optimization, Combinatorica, 1, 169-197, (1981) · Zbl 0492.90056
[13] Hadlock, F.O., Finding a maximum cut of planar graph in polynomial time, SIAM J. comput., 4, 221-225, (1975) · Zbl 0321.05120
[14] Ore, O., ()
[15] Orlova, G.I.; Dorfman, Y.G., Finding the maximum cut in a planar graph, Engrg. cybernetics, 10, 502-506, (1975) · Zbl 0247.05151
[16] Padberg, M.; Rao, M.R., Odd minimum cuts and b-matching, Math. oper. res., 7, 67-80, (1982) · Zbl 0499.90056
[17] Seymour, P.D., On Tutte’s extension of the four-colour problem, J. combin. theory ser. B., 31, 82-94, (1982) · Zbl 0471.05031
[18] Wagner, K., Beweis einer abschwächung der hadwiger-vermutung, Math. ann., 153, 139-141, (1964) · Zbl 0192.30002
[19] Wagner, K., Graphentheorie, (1970), Hochschultaschenbücher-Verlag · Zbl 0195.54103
[20] Yannakakis, M., Node- and edge-deletion NP-complete problems, (), 253-264 · Zbl 1282.68131
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.