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 […]
ACM
Flows with demands
1. Overview In a normal flow network the flow of an edge is only limited by the capacity $c(e)$ from above and by 0 from […]
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 […]
Lowest Common Ancestor – Tarjan’s off-line algorithm
We have a tree $G$ with $n$ nodes and we have $m$ queries of the form $(u, v)$. For each query $(u, v)$ we want […]
Solve RMQ (Range Minimum Query) by finding LCA (Lowest Common Ancestor)
Given an array A[0..N-1]. For each query of the form [L, R] we want to find the minimum in the array A starting from position L and ending with position R. We will […]
Lowest Common Ancestor – Farach-Colton and Bender Algorithm
Let $G$ be a tree. For every query of the form $(u, v)$ we want to find the lowest common ancestor of the nodes $u$ […]
Lowest Common Ancestor – Binary Lifting
Let $G$ be a tree. For every query of the form (u, v) we want to find the lowest common ancestor of the nodes u and v, i.e. we want […]
Lowest Common Ancestor
1. Lowest Common Ancestor – $O(\sqrt{N})$ and $O(\log N)$ with $O(N)$ preprocessing Given a tree $G$. Given queries of the form $(v_1, v_2)$, for each […]
Finding the Eulerian path in $O(M)$
A Eulerian path is a path in a graph that passes through all of its edges exactly once. A Eulerian cycle is a Eulerian path […]
Finding a negative cycle in the graph
You are given a directed weighted graph $G$ with $N$ vertices and $M$ edges. Find any cycle of negative weight in it, if such a […]
Checking a graph for acyclicity and finding a cycle in $O(M)$
Consider a directed or undirected graph without loops and multiple edges. We have to check whether it is acyclic, and if it is not, then […]
Prüfer code
In this article we will look at the so-called Prüfer code (or Prüfer sequence), which is a way of encoding a labeled tree into a sequence of […]
Kirchhoff’s theorem. Finding the number of spanning trees
Problem: You are given a connected undirected graph (with possible multiple edges) represented using an adjacency matrix. Find the number of different spanning trees of […]
Second best Minimum Spanning Tree – Using Kruskal and Lowest Common Ancestor
A Minimum Spanning Tree $T$ is a tree for the given graph $G$ which spans over all vertices of the given graph and has the […]
Minimum spanning tree – Kruskal with Disjoint Set Union
For an explanation of the MST problem and the Kruskal algorithm, first see the main article on Kruskal’s algorithm. In this article we will consider the […]
Minimum spanning tree – Kruskal’s algorithm
Given a weighted undirected graph. We want to find a subtree of this graph which connects all vertices (i.e. it is a spanning tree) and […]
