Databases Reference
In-Depth Information
r
w
1
w
2
w
4
w
3
w
31
w
32
Figure 5.2:
An illustration showing the execution of Algorithm
4
In what follows, we refer to each iteration of the outer loop (lines 6-22) in Algorithm
4
as
an
iteration
.Let
T
i
denote the tree
T
constructed by the end of iteration
i
of the algorithm, and let
M
i
be the matching which the algorithm outputs at the beginning of iteration
i
.
k. Then any matching in G that is different
from each of σ
1
,σ
2
..., σ
i
must satisfy the constraints implied by S
i
(u
j
) and S
e
(u
j
) for some j ,
1
Let u
1
,u
2
, ..., u
n
i
be the leaves of T
i
,
1
≤
i
≤
Lemma 5.8
≤
j
≤
n
i
.
Proof.
We prove the lemma by induction on
i
. To prove the basis of the induction for
i
1,we
observe that by the end of the first iteration the only leaves of
T
1
are the children of
r
. Moreover,
S
i
(r)
=
. Therefore, the correctness of the induction's basis follows Lemma
5.7
. For the
induction step, we assume that the statement of the lemma holds by the end of iteration
i
, and prove
that it still holds by the end of iteration
i
+
1.Let
u
1
,u
2
, ..., u
n
i
be leaves of
T
i
and let
x
1
, ..., x
n
i
+
1
be leaves of
T
i
+
1
. By the algorithm, leaves of
T
i
+
1
are obtained from leaves of
T
i
by removing some
=
S
e
(r)
=∅
