An exact algorithm for MAX CUT in sparse graphs
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
2007Journal name
Operations Research LettersVolume
35Number
3Publisher
Elsevier
Pages
403-408
Publication identifier
Metadata
Show full item recordAbstract (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-CUTRelated items
Showing items related by title and author.
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2008) Communication / Conférence
-
Della Croce, Federico; Escoffier, Bruno; Kaminski, Marcin; Paschos, Vangelis (2008) Chapitre d'ouvrage
-
Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2009) Communication / Conférence
-
Della Croce, Federico; Paschos, Vangelis (2012) Communication / Conférence
-
Paschos, Vangelis; Della Croce, Federico (2014) Article accepté pour publication ou publié