An exact algorithm for MAX-CUT in sparse graphs

被引：11

作者：

Della Croce, F.

Kaminski, M. J.

Paschos, V. Th.

机构：

[1] Rutgers State Univ, RUTCOR, Piscataway, NJ 08854 USA

[2] DAI, Politecn Torino, Turin, Italy

[3] Univ Paris 09, F-75775 Paris 16, France

来源：

OPERATIONS RESEARCH LETTERS | 2007年 / 35卷 / 03期

基金：

美国国家科学基金会;

关键词：

MAX-CUT; exact algorithm; sparse graphs;

D O I：

10.1016/j.orl.2006.04.001

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study exact algorithms for the MAX-CUT problem. Introducing a new technique, we present an algorithmic scheme that computes a maximum cut in graphs with bounded maximum degree. Our algorithm runs in time O*(2((l-(2/Delta))n)). We also describe a MAX-CUT algorithm for general graphs. Its time complexity is O*(2(mn/(m+n))). Both algorithms use polynomial space. (C) 2006 Elsevier B.V. All rights reserved.

引用

页码：403 / 408

页数：6

共 13 条

[1]

Bodlaender H. L., 2000, Nordic Journal of Computing, V7, P14

[2]

FEDIN SS, 2005, J MATH SCI, V126, P1200

[3] Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT [J].