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.
User avatar
Posts: 24
Joined: Fri Nov 01, 2013 5:50 pm
Location: Cienfuegos
Gender: None specified

Matching on Bipartite Graph, the faster algorithm.

Postby jose92 » Fri Jul 17, 2015 12:15 pm

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.

User avatar
COJ Administrator
Posts: 1968
Joined: Sun Nov 13, 2011 12:32 pm
Location: Universidad de las Ciencias Informáticas
Gender: None specified

Re: Matching on Bipartite Graph, the faster algorithm.

Postby ymondelo20 » Fri Jul 17, 2015 10:32 pm

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. ;)

Return to “Algorithms”

Who is online

Users browsing this forum: No registered users and 1 guest