Games on arbitrary graphs
Let a game be played by two players on an arbitrary graph $G$. I.e. the current state of the game is a certain vertex. The […]
Month: August 2021
K-th order statistic in O(N)
Given an array A of size N and a number K. The challenge is to find K-th largest number in the array, i.e., K-th order statistic. The basic idea – to use […]
Search the subarray with the maximum/minimum sum
Here, we consider the problem of finding a subarray with maximum sum, as well as some of its variations (including the algorithm for solving this […]
Longest increasing subsequence
We are given an array with $n$ numbers: $a[0 \dots n-1]$. The task is to find the longest, strictly increasing, subsequence in $a$. Formally we […]
Range Minimum Query
You are given an array $A[1..N]$. You have to answer incoming queries of the form $(L, R)$, which ask to find the minimum element in […]
Heavy-light decomposition
Heavy-light decomposition is a fairly general technique that allows us to effectively solve many problems that come down to queries on a tree . 1. Description Let there […]
Paint the edges of the tree
This is a fairly common task. Given a tree $G$ with $N$ vertices. There are two types of queries: the first one is to paint […]
Edge connectivity / Vertex connectivity
1. Definition Given an undirected graph $G$ with $n$ vertices and $m$ edges. Both the edge connectivity and the vertex connectivity are characteristics describing the […]
Topological Sorting
You are given a directed graph with $n$ vertices and $m$ edges. You have to number the vertices so that every edge leads from the vertex with […]
Kuhn’s Algorithm for Maximum Bipartite Matching
1. Problem You are given a bipartite graph $G$ containing $n$ vertices and $m$ edges. Find the maximum matching, i.e., select as many edges as […]
Check whether a graph is bipartite
A bipartite graph is a graph whose vertices can be divided into two disjoint sets so that every edge connects two vertices from different sets […]
Solving assignment problem using min-cost-flow
The assignment problem has two equivalent statements: Given a square matrix $A[1..N, 1..N]$, you need to select $N$ elements in it so that exactly one element is […]
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 […]
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 […]
