max planck institut
informatik

MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Balanced matchings, unbalanced ones and related problems. Katarzyna Paluch Max-Planck-Institut für Informatik - D1 Talk D1We use this to send out email in the morning. AG Audience English
Date: Thursday, 21 April 2011 15:00 30 Minutes Saarbrücken E1 4 - MPI-INF 024
 I will talk about several variations of the matching problem. One of them is as follows. Suppose we have a graph $G=(V,E)$ and a partition $V_1 \cup V_2 \cup \ldots \cup V_k$ of $V$. We would like to find such a maximum cardinality matching $M$ of $G$ in which roughly the same number of vertices of each $V_i$ are matched. More formally, we want to find such a maximum cardinality matching $M$, called {\bf balanced matching} that minimises \$max\{|s_M(V_i)-s_M(V_j)|: 1 \leq i
Name(s): Katarzyna Paluch