首页> 外文会议>Algorithms and Computation; Lecture Notes in Computer Science; 4288 >Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems
【24h】

Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems

机译:加权秩最大匹配的有效算法及相关问题

获取原文
获取原文并翻译 | 示例

摘要

We consider the problem of designing efficient algorithms for computing certain matchings in a bipartite graph G = (A∪P,ε), with a partition of the edge set as ε = ε_1 ∪ ε_2… ∪ ε_r. A matching is a set of (a,p) pairs, a ∈ A, p ∈ P such that each a and each p appears in at most one pair. We first consider the popular matching problem; an O(mn~(1/2)) algorithm to solve the popular matching problem was given in , where n is the number of vertices and m is the number of edges in the graph. Here we present an O(n~ω) randomized algorithm for this problem, where ω < 2.376 is the exponent of matrix multiplication. We next consider the rank-maximal matching problem; an O(min(mn, Cmn~(1/2))) algorithm was given in for this problem. Here we give an O(Cn~ω) randomized algorithm, where C is the largest rank of an edge used in such a matching. We also consider a generalization of this problem, called the weighted rank-maximal matching problem, where vertices in A have positive weights.
机译:我们考虑设计一个有效算法的问题,该算法用于计算二分图G =(A∪P,ε)中的某些匹配,并且将边的分区设置为ε=ε_1∪ε_2…∪ε_r。匹配是一组(a,p)对,a∈A,p∈P,使得每个a和每个p最多出现一对。我们首先考虑流行的匹配问题;在中给出了O(mn〜(1/2))算法来解决流行的匹配问题,其中n是顶点数,m是图中的边数。在这里,我们提出了一个针对该问题的O(n〜ω)随机算法,其中ω<2.376是矩阵乘法的指数。接下来,我们考虑秩最大匹配问题;为此,给出了一个O(min(mn,Cmn〜(1/2)))算法。在这里,我们给出O(Cn〜ω)随机算法,其中C是在这种匹配中使用的边缘的最大秩。我们还考虑了这个问题的推广,称为加权秩最大匹配问题,其中A中的顶点具有正权重。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号