Suppose a set of partially connected nodes:
- All nodes are in set A xor in Set B (i.e. Bipartite Graph)
- All nodes have a
- Connections in the Bipartite Graph exist if-and-only-if the (absolute) difference in
limitValue(and the Nodes are in opposing sets, obviously)
- Nodes and Connections have no other relevant properties (weights, directions, etc.)
Goal: Find a maximal Matching of the Nodes.
Whilst a normal BPG requires Ford-Fulkerson or similar to find a Maximal Matching, I suspect that a simple Greedy algorithm is sufficient to optimise this scenario, because the rules for connections exclude the sorts of situations that would break a Greedy approach.
Specifically, I think you can just order all the nodes, and then walk up the list pairing adjacent opposite-set nodes, whenever you pass them.
Is this correct? If so, how would one go about proving it?