Package com.jgalgo.alg.match

Class MatchingCardinalityBipartiteHopcroftKarp

java.lang.Object

com.jgalgo.alg.match.MatchingAlgoAbstract

com.jgalgo.alg.match.MatchingAlgoAbstractCardinality

com.jgalgo.alg.match.MatchingCardinalityBipartiteHopcroftKarp

All Implemented Interfaces:

MatchingAlgo

public class MatchingCardinalityBipartiteHopcroftKarp
extends MatchingAlgoAbstractCardinality

Hopcroft–Karp maximum unweighted matching algorithm for undirected bipartite graphs.

The algorithm runs in $O(m \sqrt{n})$ and it uses linear space.

Based on "A n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs" by J. Hopcroft and R. Karp (1973).

Author:

Barak Ugav

See Also:

• Wikipedia

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.match.MatchingAlgo

MatchingAlgo.Builder

Constructor Summary

Constructors

Constructor	Description
MatchingCardinalityBipartiteHopcroftKarp()	Create a new maximum matching object.

Method Summary

Methods inherited from class com.jgalgo.alg.match.MatchingAlgoAbstract

computeMaximumMatching, computeMaximumPerfectMatching, computeMinimumMatching, computeMinimumPerfectMatching

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

MatchingCardinalityBipartiteHopcroftKarp

public MatchingCardinalityBipartiteHopcroftKarp()

Create a new maximum matching object.