Maximum Cut

Given a graph $G=(V, E)$ with edge weights $c_e > 0$ for all $e\in E$ , find a cut $\delta(W)$ such that $c(\delta(W)):=\Sigma_{e\in \dela(W)} c_e$ is as large as possible.

Parameters

$n$ : number of vertices
$m$ : number of edges

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 7 of 7 algorithms


Croce, Kaminski, and Paschos	2007	$O^*(2^{mn/(m+n)})$
Koivisto	2006	$\tilde{O}(mn 2^{\omega * n / 3})$
Ryan Williams	2005	$O(m^3 2^{\omega * n / 3})$
Scott and Sorkin	2004	$O^*(2^{19m/100})$
Kulikov and Fedin	2002	$O^*(2^{m/4})$
Gramm, Hirsch, Niedermeier, and Rossmanith	2000	$O^*(2^{m/3})$
Brute Force	1975	$O(m 2^n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms