The Library
Efficient algorithms for weighted rank-maximal matchings and related problems
Tools
Kavitha, T. and Shah, C. (2006) Efficient algorithms for weighted rank-maximal matchings and related problems. In: Asano, Tetsuo, (ed.) Algorithms and Computation. Lecture Notes in Computer Science, Volume 4288 . Springer Verlag, pp. 153-162. ISBN 9783540496946
PDF
fulltext15.pdf Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (408Kb) |
Official URL: http://dx.doi.org/10.1007/11940128_17
Abstract
We consider the problem of designing efficient algorithms for computing certain matchings in a bipartite graph $G =({\mathcal{A}} \cup {\mathcal{P}}, {\mathcal{E}})$ , with a partition of the edge set as ${\mathcal{E}} = {\mathcal{E}}_1 {\mathbin {\dot{\cup}}} {\mathcal{E}}_2 \ldots {\mathbin {\dot{\cup}}} {\mathcal{E}}_r$ . A matching is a set of (a, p) pairs, $a \in {\mathcal{A}}, p\in{\mathcal{P}}$ such that each a and each p appears in at most one pair. We first consider the popular matching problem; an $O(m\sqrt{n})$ algorithm to solve the popular matching problem was given in [3], 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,Cm\sqrt{n}))$ algorithm was given in [7] 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 ${\mathcal{A}}$ have positive weights.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer Verlag | ||||
ISBN: | 9783540496946 | ||||
Book Title: | Algorithms and Computation | ||||
Editor: | Asano, Tetsuo | ||||
Official Date: | 2006 | ||||
Dates: |
|
||||
Volume: | Volume 4288 | ||||
Page Range: | pp. 153-162 | ||||
DOI: | 10.1007/11940128_17 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |