  Given a bipartite graph, where the two sets of vertices are applicants and
posts and ranks on the edges represent preferences of applicants over posts, a
{\em rank-maximal} matching is one in which the maximum number of applicants is
matched to their rank one posts and subject to this condition, the maximum
number of applicants is matched to their rank two posts, and so on. We study
the dynamic version of the problem in which a new applicant or post may be
added to the graph and we would like to maintain a rank-maximal matching. We
show that after the arrival of one vertex, we are always able to update the
existing rank-maximal matching in $\mathcal{O}(\min(c'n ,n^2) + m)$ time, where
$n$ denotes the number of applicants, $m$ the number of edges and $c'$ the
maximum rank of an edge in an optimal solution. Additionally, we update the
matching using a minimal number of changes (replacements). All cases of a
deletion of a vertex/edge and an addition of an edge can be reduced to the
problem of handling the addition of a vertex. As a by-product, we also get an
analogous $\mathcal{O}(m)$ result for the dynamic version of the (one-sided)
popular matching problem.
  Our results are based on the novel use of the properties of the
Edmonds-Gallai decomposition. The presented ideas may find applications in
other (dynamic) matching problems.
