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.
展开▼
