### Minimum-cost flow – Successive shortest path algorithm

2021

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 […]

### Flows with demands

2021

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

2021

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

2021

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

2021

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

2021

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

2021

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

2021

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)

2021

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

2021

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

2021

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

2021

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)$

2021

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

2021

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)$

2021

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

2021

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

2021

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

2021

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

2021

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

2021

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 […]