MAX CUT in cubic graphs

DOI10.1016/J.JALGOR.2004.06.001MaRDI QIDQ3159488zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Eran Halperin, Dror Livnat, Uri Zwick

Publication date 16 February 2005

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jalgor.2004.06.001

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Semidefinite programming (90C22) Approximation algorithms (68W25)

Recommendations

• Improved approximation of Max-Cut on graphs of bounded degree
• Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
• On max cut in cubic graphs
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• scientific article; zbMATH DE number 1500552

Cited in

(14)

• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold
• scientific article; zbMATH DE number 176747 (Why is no real title available?)
• On max cut in cubic graphs
• Cubical coloring -- fractional covering by cuts and semidefinite programming
• MAX-CUT has a randomized approximation scheme in dense graphs
• Maximum directed cuts in digraphs with degree restriction
• Local approximation of the maximum cut in regular graphs
• Linear-Time Approximation Algorithms for the Max Cut Problem
• Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
• Improved approximation of Max-Cut on graphs of bounded degree
• High-multiplicity cyclic job shop scheduling
• Maximum directed cuts in graphs with degree constraints
• A review on quantum approximate optimization algorithm and its variants

This page was built for publication: MAX CUT in cubic graphs

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