Databases Reference
In-Depth Information
Algorithm 5
Compute a Matching
1:
ComputeMatching(
G(V , E), S
i
,S
e
):
2:
E
←
E
\
S
e
3:
for
each
(u, v)
S
i
do
4:
for
each
e
adjacent on
u
or
v
in
G
do
5:
E
←
E
\{
e
}
6:
end for
7:
end for
8:
σ
←
A
best
(G
(V , E
))
9:
σ
←
σ
∪
S
i
10:
return
σ
∈
matching among the matchings that exclude
e
22
yet include
e
11
. After expanding all the root's
children to the desired level, we choose the leaf with maximum weight. In this case, it is
w
3
with
weight 0
.
3674.
σ(w
3
)
={
e
11
,e
22
,e
33
,e
44
}
is the second-best matching (the same result as obtained
by algorithms
2
and
3
). In the next iteration, we expand
w
3
. Consider, for example,
w
31
.
S
e
(w
31
)
=
. These two edges are excluded from
σ(w
31
)
.
e
34
stems from
σ
1
while
e
33
stems from
σ
2
.
The third iteration starts after all of
w
3
's children are found. The node with the maximum weight
among all the nodes in the tree's frontier is now
w
4
. Therefore,
σ(w
4
)
={
e
11
,e
22
,e
34
{
e
34
,e
33
}
}
is chosen
to be
σ
3
, the third-best matching.
Next, we prove the correctness of the algorithm.
Lemma 5.6
Procedure ComputeMatching(G(V , E), S
i
,S
e
) constructs a maximum weight matching
over matchings in G that contain edges from S
i
and do not contain edges from S
e
.
Proof.
The correctness of the lemma follows immediately by observing that any matching in
G
that contains
S
i
and does not contain any edge from
S
e
is also a matching in the graph
G
(V , E
)
,
constructed by the procedure ComputeMatching(
G(V , E), S
i
,S
e
).
Lemma 5.7
Let w be a node in the tree T constructed by Algorithm
4
and let w
1
, ..., w
t
be all the
children of w in T . Then any matching satisfying constraints implied by S
i
(w), S
e
(w), and different from
σ(w)must satisfy constraints implied by S
i
(w
j
), S
e
(w
j
) for some j ,
1
≤
j
≤
t .
Proof.
The correctness of the lemma follows by the definition of
S
i
(w
j
)
,
S
e
(w
j
)
, 1
≤
j
≤
k
and by
the fact that for any matching
σ
different from
σ(w)
there exists an edge
e
∈
σ(w)
such that
e
∈
σ
.
