Maximum Cut (Maximum Cut)

Description

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

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Hadlock	1975	$O({2}^V)$		Exact	Deterministic

Time Complexity graph

Error creating thumbnail: Unable to save thumbnail to destination