Optimization via enumeration: A new algorithm for the max cut problem

DOI10.1007/S101070100217MaRDI QIDQ5935710zbMATH OpenFDO

Authors A. Galluccio, Martin Loebl, Jan Vondrák

Publication date 26 June 2001

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

cutgenerating functionmodular arithmeticsPfaffian orientation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Partitioning planar graphs: a fast combinatorial approach for max-cut
• New algorithms for the weighted maximum cut problem on graphs
• The maximum cut problem
• Optimization and optimality test for the Max-Cut Problem
• An exact algorithm for MAX-CUT in sparse graphs

Cited in

(20)

• Computation of sparse circulant permanents via determinants
• \(\mathrm{PUBO}_i\): a tunable benchmark with variable importance
• Subextensive singularity in the 2D \(\pm J\) Ising spin glass
• Cut-and-solve: An iterative search strategy for combinatorial optimization problems
• Aspect-ratio scaling of domain wall entropy for the 2D \(\pm J\) Ising spin glass
• Efficient polynomial-time algorithms for special graph partitioning problems
• Max-Cut and containment relations in graphs
• The maximum cut problem
• Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
• Optimization and optimality test for the Max-Cut Problem
• \textsc{max-cut} and containment relations in graphs
• scientific article; zbMATH DE number 1750489 (Why is no real title available?)
• Tight cycle relaxations for the cut polytope
• Complexity and polynomially solvable special cases of QUBO
• scientific article; zbMATH DE number 7559431 (Why is no real title available?)
• Counting shortest two disjoint paths in cubic planar graphs with an NC algorithm
• Maximum cut parameterized by crossing number
• Killing a vortex
• Optimal cuts in graphs and statistical mechanics
• Geometric representations of binary codes and computation of weight enumerators

This page was built for publication: Optimization via enumeration: A new algorithm for the max cut problem

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