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

DOI10.1007/BF02591727MaRDI QIDQ3315282zbMATH OpenOpenAlexWikidataFDO

Authors Martin Grötschel, G. L. Nemhauser

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)

Recommendations

• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• Max-cut in circulant graphs
• scientific article; zbMATH DE number 176747
• scientific article; zbMATH DE number 780784
• On the kernelization complexity of problems on graphs without long odd cycles

Cites work

• scientific article; zbMATH DE number 3547323 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3390827 (Why is no real title available?)
• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• Depth-First Search and Linear Graph Algorithms
• 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
• Weakly bipartite graphs and the max-cut problem

Cited in

(26)

• Intersections of cycles in \(k\)-connected graphs
• On the cut polytope
• On deletions of largest bonds in graphs
• scientific article; zbMATH DE number 4193718 (Why is no real title available?)
• On two conjectures about the intersection of longest paths and cycles
• Polynomial kernels for vertex cover parameterized by small degree modulators
• Graph theory (algorithmic, algebraic, and metric problems)
• \textsc{max-cut} and containment relations in graphs
• Complexity and polynomially solvable special cases of QUBO
• Max-Cut and containment relations in graphs
• The line index and minimum cut of weighted graphs
• A polynomial characterization of some graph partitioning problems
• scientific article; zbMATH DE number 6004865 (Why is no real title available?)
• Max-cut in circulant graphs
• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• Maximum cut on line and total graphs
• Maximum cut parameterized by crossing number
• A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
• Pairs of largest circuits in 3-connected matroids
• Quantum annealing versus digital computing. An experimental comparison
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Intersections of largest bonds in \(k\)-connected graphs
• Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
• Intersections of longest cycles in \(k\)-connected graphs
• Largest circuits in matroids
• On the kernelization complexity of problems on graphs without long odd cycles

This page was built for publication: A polynomial algorithm for the max-cut problem on graphs without long odd cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3315282)