  Baswana, Gupta and Sen [FOCS'11] showed that fully dynamic maximal matching
can be maintained in general graphs with logarithmic amortized update time.
More specifically, starting from an empty graph on $n$ fixed vertices, they
devised a randomized algorithm for maintaining maximal matching over any
sequence of $t$ edge insertions and deletions with a total runtime of $O(t \log
n)$ in expectation and $O(t \log n + n \log^2 n)$ with high probability.
Whether or not this runtime bound can be improved towards $O(t)$ has remained
an important open problem. Despite significant research efforts, this question
has resisted numerous attempts at resolution even for basic graph families such
as forests.
  In this paper, we resolve the question in the affirmative, by presenting a
randomized algorithm for maintaining maximal matching in general graphs with
\emph{constant} amortized update time. The optimal runtime bound $O(t)$ of our
algorithm holds both in expectation and with high probability.
  As an immediate corollary, we can maintain 2-approximate vertex cover with
constant amortized update time. This result is essentially the best one can
hope for (under the unique games conjecture) in the context of dynamic
approximate vertex cover, culminating a long line of research.
  Our algorithm builds on Baswana et al.'s algorithm, but is inherently
different and arguably simpler. As an implication of our simplified approach,
the space usage of our algorithm is linear in the (dynamic) graph size, while
the space usage of Baswana et al.'s algorithm is always at least $\Omega(n \log
n)$.
  Finally, we present applications to approximate weighted matchings and to
distributed networks.
