Optimization and optimality test for the Max-Cut Problem

DOI10.1007/BF01415982zbMath0701.90090OpenAlexW2126014649MaRDI QIDQ3479833

Chr. Hohmann, Walter Kern

Publication date: 1990

Published in: [https://portal.mardi4nfdi.de/entity/Q3031760 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

rescalingmax-cut problembinary searchpolynomial 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)

Related Items (1)

A general approach to the calculation of stability radii for the max-cut problem with multiple criteria

Cites Work

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

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