The authors present two algorithms for the Rank-Maximal Matching Problem. The first one is a combinatorial algorithm with running time O(min(n+ C, C sqrt(n))m) where C <= the maximal rank of an edge used in the rank-maximal matching. The authors also present a O(Cnm) time algorithm which transform the rank-maximal matching problem into a maximum weight matching problem. However, I will only present the first algorithm.
From: Rank-Maximal Matchings by R.W. Irving, T.Kavitha, K. Mehlorn, D. Michail, and K. Paluch. Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004.