in reply to decomposing binary matrices

A bipartite graph is a graph where the vertices are partitioned into 2 sets, and every edge crosses between these sets (i.e, does not stay within a set). In this case, one set denotes your variables and the other set denotes your values. Draw an edge between a variable and a value if it is legal to assign that value to that variable.

A matching is a subset of edges from a graph, where no two edges share an endpoint. Since all edges in a bipartite graph run between these 2 sets, you can think of a matching as a (partial) mapping from 1 set to the other (each vertex in set A is paired with at most 1 vertex in set B). In this case, it represents a mapping from variables to values. Since the matching is a subset of the available edges, the mapping doesn't include any assignments that you have deemed "illegal".

What you want is a *perfect* matching, one that covers all vertices (so it's a 1-to-1 mapping between variables and values). Usually this problem is phrased as the "marriage problem" -- The two sets of vertices are men & women, and there is an edge between a man & a woman if they could be happy married. You want to know if there is a way to pair them up so that each couple is happy (and if there is such a way to pair them up, output it).

An example that I found with pictures is here: bipartite matching. Googling for bipartite matching algorithm turns up plenty of hits. I know that there are efficient algorithms for doing it, but can't remember all of the details.

blokhead

Replies are listed 'Best First'. | |
---|---|

Re^2: decomposing binary matrices
by hv (Parson) on Feb 16, 2007 at 17:37 UTC | |

Re^2: decomposing binary matrices
by hv (Parson) on Feb 17, 2007 at 13:30 UTC |

Comment onRe: decomposing binary matrices