The max-cut problem on graphs not contractible to \(K_ 5\)

DOI10.1016/0167-6377(83)90016-0zbMath0525.90094OpenAlexW2060660073MaRDI QIDQ593988

Publication date: 1983

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(83)90016-0

zbMATH Keywords

decomposition NP-completeness polynomial algorithm max-cut problem ellipsoid method polyhedron of cuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)

Related Items

On the cycle polytope of a binary matroid, A solvable case of quadratic 0-1 programming, Decomposition and optimization over cycles in binary matroids, Complexity and Polynomially Solvable Special Cases of QUBO, Application of cut polyhedra. I, Applications of cut polyhedra. II, Unnamed Item, One-node cutsets and the dominating set polytope, A decomposition theory for matroids. IV: Decomposition of graphs, Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem, A nonmonotone GRASP, A polynomial characterization of some graph partitioning problems, On decomposability of multilinear sets, Computing convex hulls and counting integer points with \texttt{polymake}, Hilbert bases of cuts, Generalized cut and metric polytopes of graphs and simplicial complexes, Quantum Annealing versus Digital Computing, On the bond polytope, On tail dependence matrices. The realization problem for parametric families, Computing the Grothendieck constant of some graph classes, Minimizing breaks by maximizing cuts., Complexity of maximum cut on interval graphs, Approximating sparse quadratic programs, A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs, Partitioning planar graphs: a fast combinatorial approach for max-cut, Maximum Cut Parameterized by Crossing Number, \textsc{max-cut} and containment relations in graphs, Cuts in undirected graphs. I, Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, Seminormality, canonical modules, and regularity of cut polytopes, A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO), A new graph parameter related to bounded rank positive semidefinite matrix completions, Compositions in the bipartite subgraph polytope, Facets for the cut cone. I, On cuts and matchings in planar graphs, Ideal clutters, Optimal cuts in graphs and statistical mechanics, Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem, Max-multiflow/min-multicut for G+H series-parallel, max-cut and Containment Relations in Graphs, A novel formulation of the max-cut problem and related algorithm, Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem, On the extension complexity of combinatorial polytopes, Formulations and valid inequalities of the node capacitated graph partitioning problem, Enumeration of the facets of cut polytopes over some highly symmetric graphs, On fractional cut covers, On the cut polytope, Master polytopes for cycles of binary matroids, The cut polytope and the Boolean quadric polytope, Role of redundant constraints for improving dual bounds in polynomial optimization problems, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, Global convergence of the alternating projection method for the Max-Cut relaxation problem, The line index and minimum cut of weighted graphs, Maximum cut on line and total graphs, A characterization of weakly bipartite graphs, On some weakly bipartite graphs, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, Node and edge relaxations of the max-cut problem, A fast algorithm for minimum weight odd circuits and cuts in planar graphs

Cites Work