A Decomposition Theorem for Maximum Weight Bipartite Matchings
A Decomposition Theorem for Maximum Weight Bipartite Matchings
复制标题
最大权二分匹配的分解定理
DOI：
10.1137/s0097539799361208
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
H. Ting
中科院分区：
文献类型：
--
作者：
M. Kao;T. Lam;W. Sung;H. Ting
令G为边缘上的正整数且没有孤立的节点的两部分图。令n，n和w为节点计数，最大的边缘重量，而G。L。k（x，y）的总重量为log x / log（x2 / y）。我们提出了一种新的分解定理，用于最大重量双分匹配，并使用它来设计$ o（\ sqrt {n} w / k（n，w / n））$ - 计算G的最大重量匹配的时间算法。这算法在计算最大重量匹配的最佳时间复杂性与计算最大基数匹配的最大时间复杂性之间存在一个长期的差距。给定G和G的最大重量匹配，我们可以进一步计算O（W）时间中所有节点U的G - {U}的最大重量匹配的重量。
Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n, N, and W be the node count, the largest edge weight, and the total weight of G. Let k(x, y) be log x / log (x2/y). We present a new decomposition theorem for maximum weight bipartite matchings and use it to design an $O(\sqrt{n}W / k(n, W/N))$-time algorithm for computing a maximum weight matching of G. This algorithm bridges a long-standing gap between the best known time complexity of computing a maximum weight matching and that of computing a maximum cardinality matching. Given G and a maximum weight matching of G, we can further compute the weight of a maximum weight matching of G - {u} for all nodes u in O(W) time.