# Bipartite Matching

## Descriptionβ

A bipartite graph is a graph in which we can divide vertices into **two
independent sets**, such that every edge connects vertices between these sets.
No connection can be established within the set.

Matching in bipartite graphs (**bipartite
matching**) is
described as a set of edges that are picked in a way to **not share an
endpoint**. Furthermore, maximum matching is such matching of maximum
cardinality of the chosen edge set. The algorithm runs in **O(|V|*|E|)** time,
where V represents a set of nodes and E represents a set of edges.

This little tool can become extremely handful when calculating assignments between entities. Assigning stuff between two sets of entities is done in a large number of industries, and therefore having a method to find it can make the developing process easier.

Example of maximum matching between two sets of nodes in the bipartite graph

## Materialsβ

### Implementationβ

**Bipartite matching** is implemented as part of the
**MAGE** project. Be sure to check it out in
the link above. βοΈ

## Use casesβ

To optimize transportation in nowadays successful and widely used applications like Uber, Lyft or Bolt, a crucial moment is assigning drivers with potential passengers. To minimize the overall waiting time, the process calculates that assignment by finding optimal matching with a bipartite graph.