首页 | 本学科首页   官方微博 | 高级检索  
     


MAX CUT in cubic graphs
Authors:Eran Halperin   Dror Livnat  Uri Zwick  
Affiliation:a Computer Science Division, University of California at Berkeley, Berkeley, CA 94720-1776, USA;b School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel
Abstract:We present an improved semidefinite programming based approximation algorithm for the MAX CUT problem in graphs of maximum degree at most 3. The approximation ratio of the new algorithm is at least 0.9326. This improves, and also somewhat simplifies, a result of Feige, Karpinski and Langberg. We also observe that results of Hopkins and Staton and of Bondy and Locke yield a simple combinatorial 4/5-approximation algorithm for the problem. Finally, we present a combinatorial 22/27-approximation algorithm for the MAX CUT problem for regular cubic graphs.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号