Joanna Jasinska: t-matchings via half-edges (Paper by Paluch and Wasylkiewicz)

Applied Discrete Math seminar

Abstract:

In this talk we will present simple combinatorial algorithms for the problem
of finding a maximum size/weight K_{t,t}-free t-matching for a bipartite graph
G, both in a special case of t=2 and in a general case t>2. It is known that
the weighted versions of those problems are NP-hard, thus we will assume that
the weights are vertex-induced on any subgraph isomorphic to K_{t,t}. In the
presented algorithms authors used the idea of the so-called half-edges.