MAX CUT in cubic graphs

被引：32

作者：

Halperin, E

Livnat, D

Zwick, U ^{[1
]}

机构：

[1] Univ Calif Berkeley, Div Comp Sci, Berkeley, CA 94720 USA

[2] Tel Aviv Univ, Sch Comp Sci, IL-69978 Tel Aviv, Israel

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2004年 / 53卷 / 02期

基金：

以色列科学基金会;

关键词：

D O I：

10.1016/j.jalgor.2004.06.001

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (C) 2004 Elsevier Inc. All rights reserved.

引用

页码：169 / 185

页数：17

共 12 条

[1]

Berman P., 1999, Automata, Languages and Programming. 26th International Colloquium, ICALP'99. Proceedings (Lecture Notes in Computer Science Vol.1644), P200

[2] LARGEST BIPARTITE SUBGRAPHS IN TRIANGLE-FREE GRAPHS WITH MAXIMUM DEGREE 3 [J].