What is a non-bipartite matching problem and what are some of the real life applications of non-bipartite matching?

257 Views Asked by At

I know what bipartite matching is. In bipartite matching, we look for a one-to-one match between two disjoint sets of vertices. A classic real-life example of bipartite matching is matching kidneys. I am wondering what non-bipartite matching is really about and where we may want to solve non-bipartite matching problems in real life.

  1. Does non-bipartite matching refers to cases where we have more than two disjoint sets of vertices (such as tripartite)?
  2. Does non-bipartite matching mean that we have a bipartite network, but we can also have matching within a specific set?
    1. and 2. both can happen?