Integer Maximum Flow

Maximum flow problems involve finding a feasible flow through a flow network that is maximum. In this variant, the capacities must be integers.

Parameters

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

Related Problems

st-Maximum Flow

ST-Maximum Flow

Minimum-Cost Flow

All-Pairs Maximum Flow

Maximum Local Edge Connectivity

dynamic st-Maximum Flow

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 3 of 3 algorithms

				See more
Goldberg & Rao	1997	$O(E^{1.5} \log(V^2/E) \log U)$	$O(V + E)$
Goldberg & Rao	1997	$O(V^{0.66}E \log(V^2/E) \log U)$	$O(V + E)$
Ahuja, Orlin, Tarjan	1987	$O(VE \log((V \log U)/(E \log \log U) + 2))$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table