Matching on Bipartite Graph, the faster algorithm.

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
Post Reply
User avatar
jose92
Posts: 24
Joined: 7 years ago
Location: Cienfuegos
Gender: None specified

Matching on Bipartite Graph, the faster algorithm.

Post by jose92 » 6 years ago

I always have used an augmenting recursive algorithm for finding maximum bipartite matching but I have recently figure it out that sometimes it is not fast enoght. Can anyone sugest and explain what algorithm should I use in order to increase performance when solving this classical problem.
Thanks in advance.


Top
User avatar
ymondelo20
Posts: 1968
Joined: 9 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:
Contact ymondelo20

Re: Matching on Bipartite Graph, the faster algorithm.

Post by ymondelo20 » 6 years ago

Just figure out the problem like a maximum flow problem. In almost all cases it´s possible to apply that.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)
Top
Post Reply

Return to “Algorithms”