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

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

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

(19)

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

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)