  We study the Maximum Cardinality Matching (MCM) and the Maximum Weight
Matching (MWM) problems, on trees and on some special classes of graphs, in the
Online Preemptive and the Incremental Dynamic Graph models. In the {\em Online
Preemptive} model, the edges of a graph are revealed one by one and the
algorithm is required to always maintain a valid matching. On seeing an edge,
the algorithm has to either accept or reject the edge. If accepted, then the
adjacent edges are discarded, and all rejections are permanent. In this model,
the complexity of the problems is settled for deterministic algorithms. Epstein
et al. gave a $5.356$-competitive randomized algorithm for MWM, and also proved
a lower bound of $1.693$ for MCM. The same lower bound applies for MWM.
  In this paper we show that some of the results can be improved in the case of
trees and some special classes of graphs. In the online preemptive model, we
present a $64/33$-competitive (in expectation) randomized algorithm for MCM on
trees.
  Inspired by the above mentioned algorithm for MCM, we present the main result
of the paper, a randomized algorithm for MCM with a "worst case" update time of
$O(1)$, in the incremental dynamic graph model, which is $3/2$-approximate (in
expectation) on trees, and $1.8$-approximate (in expectation) on general graphs
with maximum degree $3$. Note that this algorithm works only against an
oblivious adversary. Hence, we derandomize this algorithm, and give a $(3/2 +
\epsilon)$-approximate deterministic algorithm for MCM on trees, with an
amortized update time of $O(1/\epsilon)$.
  We also present a minor result for MWM in the online preemptive model, a
$3$-competitive (in expectation) randomized algorithm on growing trees (where
the input revealed upto any stage is always a tree, i.e. a new edge never
connects two disconnected trees).
