MAX CUT in cubic graphs

DOI10.1016/J.JALGOR.2004.06.001zbMATH Open1089.68077DBLPjournals/jal/HalperinLZ04OpenAlexW1965444148WikidataQ60299155 ScholiaQ60299155MaRDI QIDQ3159488FDOQ3159488

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

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

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)

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
• Title not available (Why is that?)
• 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)