I was wondering if there exists a way to compute the size of the maximum matching in a bipartite graph without having to compute the maximum matching itself. Any help or direction will be really appreciated.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
You could find the minimum vertex cover. According to the König-Egerváry Theorem, the minimum vertex cover is the same size as a maximum matching of any bipartite graph.