st-Maximum Flow

A flow network is a graph where each edge has a capacity and each edge receives a flow. The sum of the flows into a vertex equals the sum of the flows exiting that vertex. s is generally a source, a vertex that only has outgoing edges, and t is a sink, a vertex with only incoming edges. The goal is to find the maximum quantity of flow that can travel from $s$ to $t$ without exceeding the capacities of any edge along the way.

Parameters

$V$ : number of vertices
$E$ : number of edges
$U$ : maximum edge capacity

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 6 of 6 algorithms


James B Orlin's + KRT (King; Rao; Tarjan)'s algorithm	2013	$O(VE)$	$O(V + E)$
Phillips & Westbrook	1993	$O(VE(\log(V)/\log(V/E) + (\log V)^2))$	$O(V + E)$
King et al. (KRT)	1992	$O(VE + V^{2+\epsilon})$	$O(V + E)$
Cheriyan et al.	1990	$O(V^3 / \log V)$	$O(V + E)$
Alon	1990	$O(VE + V^{2.66} \log V)$	$O(V + E)$
Cheriyan & Hagerup	1989	$O(VE \log V)$	$O(V + E)$

Reductions Table

Displaying 2 of 2 reductions

			See more
MaxSAT	st-Maximum Flow	2018
MaxSAT	st-Maximum Flow	2018

Other relevant algorithms

Insuffient Data to display table