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

Related Problems

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 1 of 1 algorithms

				See more
Brute Force	1975	$O(m 2^n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table