Skip to main content

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.

drawing

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

Materials​

Implementation​

Bipartite Matching

Bipartite Matching

Bipartite matching is implemented as part of the MAGE project. Be sure to check it out in the link above. ☝️

Use cases​

Transportation

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.