论文标题
两分图的真正多项式最小重量完美匹配
A Real Polynomial for Bipartite Graph Minimum Weight Perfect Matchings
论文作者
论文摘要
在最近的一篇论文中，Beniamini和Nisan为布尔功能提供了封闭式的公式，以确定给定的两部分图$ g \ subseteq k_ {n，n，n} $是否具有完美的匹配，并具有有效的算法以及计算该多元素元的系数的有效算法。我们给出以下概括：给定$ k_ {n，n} $边缘的任意非负权重函数$ w $，请考虑其最小重量完美匹配的集合。我们为布尔函数提供了真实的多连线多项式，该函数确定图形$ g \ subseteq k_ {n，n，n} $包含这些最小重量完美匹配之一。
In a recent paper, Beniamini and Nisan gave a closed-form formula for the unique multilinear polynomial for the Boolean function determining whether a given bipartite graph $G \subseteq K_{n,n}$ has a perfect matching, together with an efficient algorithm for computing the coefficients of the monomials of this polynomial. We give the following generalization: Given an arbitrary non-negative weight function $w$ on the edges of $K_{n,n}$, consider its set of minimum weight perfect matchings. We give the real multilinear polynomial for the Boolean function which determines if a graph $G \subseteq K_{n,n}$ contains one of these minimum weight perfect matchings.
