Title: Dynamic Rank Maximal Matchings,
Abstract: We consider the problem of matching applicants to posts where applicants have
preferences over posts. Thus the input to our problem is a bipartite graph G =
(A U P,E), where A denotes a set of applicants, P is a set of posts, and there
are ranks on edges which denote the preferences of applicants over posts. A
matching M in G is called rank-maximal if it matches the maximum number of
applicants to their rank 1 posts, subject to this the maximum number of
applicants to their rank 2 posts, and so on.
We consider this problem in a dynamic setting, where vertices and edges can
be added and deleted at any point. Let n and m be the number of vertices and
edges in an instance G, and r be the maximum rank used by any rank-maximal
matching in G. We give a simple O(r(m+n))-time algorithm to update an existing
rank-maximal matching under each of these changes. When r = o(n), this is
faster than recomputing a rank-maximal matching completely using a known
algorithm like that of Irving et al., which takes time O(min((r + n,
r*sqrt(n))m).