New algorithms for the weighted maximum cut problem on graphs

DOI10.1007/BF02366923zbMath0841.05085OpenAlexW2032739865MaRDI QIDQ1907796

Naum Z. Shor, O. A. Berezovskyi

Publication date: 27 March 1996

Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)

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

zbMATH Keywords

algorithmnonsmooth optimizationNP-completeweighted maximum cut problemtheory of dual estimates

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

On the problem of packing spheres in a cube ⋮ New quadratic models for the maximum weighted cut problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weakly bipartite graphs and the max-cut problem
• Laplacian eigenvalues and the maximum cut problem
• Beweis einer Abschwächung der Hadwiger-Vermutung
• Exact cuts in networks
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Linear Matrix Inequalities in System and Control Theory
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Node-and edge-deletion NP-complete problems

This page was built for publication: New algorithms for the weighted maximum cut problem on graphs