Skip to main content

bipartite_matching

docs-source

Abstract#

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.

TraitValue
Module typealgorithm
ImplementationC++
Graph directionundirected
Edge weightsunweighted
Parallelismsequential

Procedures#

max()#

Output:#

  • maximum_bipartite_matching ➡ Maximum bipartite matching, the cardinality of maximum matching edge subset. If graph is not bipartite, zero(0) is returned value.

Usage:#

CALL bipartite_matching.max()YIELD maximum_bipartite_matching;

Example#