An exact algorithm for MAX CUT in sparse graphs

Kaminski, Marcin; Della Croce, Federico; Paschos, Vangelis

Kaminski, Marcin; Della Croce, Federico; Paschos, Vangelis (2007), An exact algorithm for MAX CUT in sparse graphs, Operations Research Letters, 35, 3, p. 403-408. http://dx.doi.org/10.1016/j.orl.2006.04.001

Type

Article accepté pour publication ou publié

External document link

http://hal.archives-ouvertes.fr/hal-00116633/en/

Date

2007

Journal name

Operations Research Letters

Volume

Number

Publisher

Elsevier

Pages

403-408

Abstract (EN)

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(1-(2/Δ))n). We also describe a MAX-CUT algorithm for general graphs. Its time complexity is O*(2mn/(m+n)). Both algorithms use polynomial space.

Subjects / Keywords

Sparse graphs; Exact algorithm; MAX-CUT