• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Workshop on Experimental and Efficient Algorithms(WEA 2005); 20050510-13; Santorini Island(GR) >Fast Algorithms for Weighted Bipartite Matching
【24h】

Fast Algorithms for Weighted Bipartite Matching

机译：加权二分匹配的快速算法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Let G = (V_1 ∪ V_2, E) be a bipartite graph on n nodes and m edges and let w : E →R_+ be a weight function on the edges. We give several fast algorithms for computing a minimum weight (perfect) matching for a given complete bipartite graph (i.e. m = n~2) by pruning the edge set. The algorithm will also output an upper bound on the achieved approximation factor. Under the assumption that the edge weights are uniformly distributed, we show that our algorithm will compute an optimal solution with high probability. From this we deduce an algorithm with fast expected running time that will always compute an optimal solution. For real edge weights we achieve a running time of O(n~2 log n) and for integer edge weights a running time of O(n~2).
机译：令G =（V_1∪V_2，E）为n个节点和m个边上的二部图，令w：E→R_ +为边上的权重函数。我们给出了几种快速算法，用于通过修剪边缘集来计算给定完整二部图（即m = n〜2）的最小权重（完美）匹配。该算法还将输出所达到的近似因子的上限。在边缘权重均匀分布的假设下，我们证明了我们的算法将以高概率计算出最优解。据此，我们推导出了一种算法，该算法具有预期的快速运行时间，将始终计算出最优解。对于实际边缘权重，我们获得的运行时间为O（n〜2 log n），对于整数边缘权重，我们获得的运行时间为O（n〜2）。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号