So I came across a problem in which there were 'n' pilots and 'm' airplanes. Each pilot had a list of airplanes which he could fly. And one pilot can fly only one airplane at a time. You had to determine the maximum number of planes that can fly at the same time. Standard bipartite matching problem(which I found out later).
In the contest, I came up with a greedy algorithm as follows :
While there are planes in the graph :
1)Select a plane which can be flown by minimum number of pilots
2)Greedily allocate a pilot to that plane (from the ones who can fly it)
3)Remove both the plane and the allocated pilot from the graph
In general, for a bipartite matching problem, I propose the following algorithm :
While there are nodes in the right set of the bipartite graph :
1)Select a node from the right set with minimum incoming degree
2)Greedily match it with ANY node from the left set (which has an edge to it)
3)Remove both these nodes from the graph( this would also involve decreasing the incoming degree of all nodes on the right to which this node has an edge to)
I am not mathematically proficient to prove the correctness of this algorithm and after a lot of thinking I have not been able to come up with a counter example. So my specific question is, is this a standard or known algorithm or am I making some blatant mistake which I cannot see?
Please feel free to edit my question to make it clearer if you feel so. Thank you.
counter-example:
a1 a2 a3 a4 a5
p1 x x
p2 x x x x
p3 x x x x
p4 x
p5 x x x
a5 is selected first. Randomly select pilot which MAY be p5. If it is, p4 doesn't have a plane.