Strongly Stable Matchings in Time O(nm)

bipartite graph $G = (X \disjointcup W, E)$
with linearly ordered adjacency lists; ties are
allowed.
A matching $M$ is a set of edges no two of which share an endpoint. An
edge $e = (a,b) \in E \setminus M$ is a \emph{blocking edge} for $M$
if $a$ is either unmatched or
strictly prefers $b$ to its partner in $M$, and $b$ is either unmatched
or strictly prefers $a$
to its partner in $M$ or is indifferent between them. A matching
is strongly stable if there is no blocking edge with respect to it.
We give an $O(nm)$ algorithm for computing strongly stable
matchings, where $n$ is the number of vertices and $m$ is the number of edges.
The previous best algorithm had running time $O(m^2)$.

Joint work with Kurt Mehlhorn, Katarzyna Paluch, Kavitha Telikepalli.