Minimum-cost flow – Successive shortest path algorithm
Given a network $G$ consisting of $n$ vertices and $m$ edges. For each edge (generally speaking, oriented edges, but see below), the capacity (a non-negative […]
flow
Maximum flow – MPM algorithm
MPM (Malhotra, Pramodh-Kumar and Maheshwari) algorithm solves the maximum flow problem in $O(V^3)$. This algorithm is similar to Dinic’s algorithm. 1. Algorithm Like Dinic’s algorithm, MPM […]
Maximum flow – Dinic’s algorithm
Dinic’s algorithm solves the maximum flow problem in $O(V^2E)$. The maximum flow problem is defined in this article Maximum flow – Ford-Fulkerson and Edmonds-Karp. This algorithm […]
Maximum flow – Push-relabel method improved
We will modify the push-relabel method to achieve a better runtime. 1. Description The modification is extremely simple: In the previous article we chosen a vertex with […]
Maximum flow – Push-relabel algorithm
The push-relabel algorithm (or also known as preflow-push algorithm) is an algorithm for computing the maximum flow of a flow network. The exact definition of […]
Maximum flow – Ford-Fulkerson and Edmonds-Karp
The Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson method for computing a maximal flow in a flow network. 1. Flow network First let’s define […]
