Given an undirected bipartite graph $G=(A \cup B, E)$, a many-to-many matching (MM) in $G$ matches each vertex $v$ in $A$ (resp. $B$) to at least one vertex in $B$ (resp. $A$). In this paper, we consider the limited-capacity many-to-many matching (LCMM) in $G$, where each vertex $v\in A\cup B$ is matched to at least one and at most $Cap(v)$ vertices; the function $Cap : A\cup B \rightarrow \mathbb{Z}> 0$ denotes the capacity of $v$ (an upper bound on its degree in the LCMM). We give an $O(n^3)$ time algorithm for finding a maximum (respectively minimum) weight LCMM in $G$ with non-positive real (respectively non-negative real) edge weights, where $\lvert A \rvert+\lvert B \rvert=n$.
翻译：给定一个无向二分图$G=(A \cup B, E)$，多对多匹配（MM）将$A$（或$B$）中的每个顶点$v$匹配到$B$（或$A$）中的至少一个顶点。本文研究$G$中的有限容量多对多匹配（LCMM），其中每个顶点$v\in A\cup B$被匹配到至少一个且至多$Cap(v)$个顶点；函数$Cap : A\cup B \rightarrow \mathbb{Z}> 0$表示$v$的容量（即其在LCMM中度数的上界）。我们提出了一种$O(n^3)$时间算法，用于在边权重为非正实数（或非负实数）的图$G$中寻找最大（或最小）权重的LCMM，其中$\lvert A \rvert+\lvert B \rvert=n$。
相关内容
微信扫码咨询专知VIP会员