Optimization and optimality test for the Max-Cut Problem

DOI10.1007/BF01415982MaRDI QIDQ3479833zbMATH OpenOpenAlexFDO

Authors Chr. Hohmann, Walter Kern

Publication date 1990

Published in ZOR Zeitschrift f�r Operations Research Methods and Models of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

rescalingbinary searchmax-cut problempolynomial transformationunweighted caseweighted caseoptimal testing oraclepolynomial equivalent optimality test

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• New algorithms for the weighted maximum cut problem on graphs
• The maximum cut problem
• Optimization via enumeration: A new algorithm for the max cut problem
• scientific article; zbMATH DE number 176747
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds

Cites work

• On finite locally projective planar spaces
• On the Complexity of Local Search for the Traveling Salesman Problem

Cited in

(4)

• Canonical dual approach to solving the maximum cut problem
• New algorithms for the weighted maximum cut problem on graphs
• Optimization via enumeration: A new algorithm for the max cut problem
• A general approach to the calculation of stability radii for the max-cut problem with multiple criteria

This page was built for publication: Optimization and optimality test for the Max-Cut Problem

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