Optimization and optimality test for the Max-Cut Problem

DOI10.1007/BF01415982zbMATH Open0701.90090OpenAlexW2126014649MaRDI QIDQ3479833FDOQ3479833

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

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

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)

Cites Work

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

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)