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

DOI10.1007/BF02591727zbMATH Open0532.90074OpenAlexW2049482546WikidataQ89048251 ScholiaQ89048251MaRDI QIDQ3315282FDOQ3315282

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

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

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)

Cites Work

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

Cited In (26)

• Intersections of cycles in \(k\)-connected graphs
• On the cut polytope
• On deletions of largest bonds in graphs
• Title not available (Why is that?)
• 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)
• Complexity and polynomially solvable special cases of QUBO
• \textsc{max-cut} and containment relations in graphs
• Max-Cut and containment relations in graphs
• The line index and minimum cut of weighted graphs
• Title not available (Why is that?)
• A polynomial characterization of some graph partitioning problems
• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• Max-cut in circulant graphs
• 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)