The Library
Efficient algorithms for weighted rankmaximal matchings and related problems
Tools
Kavitha, T. and Shah, C. (2006) Efficient algorithms for weighted rankmaximal matchings and related problems. In: Asano, Tetsuo, (ed.) Algorithms and Computation. Lecture Notes in Computer Science, Volume 4288 . Springer Verlag, pp. 153162. 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 rankmaximal 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 rankmaximal 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. 153162  
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 