A polynomial algorithm for the max-cut problem on graphs without long odd cycles

DOI10.1007/BF02591727zbMath0532.90074OpenAlexW2049482546WikidataQ89048251 ScholiaQ89048251MaRDI QIDQ3315282

Martin Grötschel, Nemhauser, George I.

Publication date: 1984

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02591727

zbMATH Keywords

combinatorial optimizationNP-completenesspolynomial time algorithmsmax-cut problemfinite, undirected loopless graphs with multiple edgeslongest odd cyclespositive edge weights

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Integer programming (90C10)

Related Items

Complexity and Polynomially Solvable Special Cases of QUBO, Unnamed Item, A polynomial characterization of some graph partitioning problems, The max-cut problem on graphs not contractible to \(K_ 5\), Intersections of longest cycles in \(k\)-connected graphs, Quantum Annealing versus Digital Computing, Maximum Cut Parameterized by Crossing Number, \textsc{max-cut} and containment relations in graphs, Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs, Pairs of largest circuits in 3-connected matroids, On deletions of largest bonds in graphs, Largest circuits in matroids, Graph theory (algorithmic, algebraic, and metric problems), max-cut and Containment Relations in Graphs, On the cut polytope, Polynomial kernels for vertex cover parameterized by small degree modulators, Intersections of largest bonds in \(k\)-connected graphs, The line index and minimum cut of weighted graphs, Maximum cut on line and total graphs, Intersections of cycles in \(k\)-connected graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weakly bipartite graphs and the max-cut problem
• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Node-and edge-deletion NP-complete problems
• On chromatic number of graphs and set-systems
• Depth-First Search and Linear Graph Algorithms