Databases Reference
In-Depth Information
and if there are still edges left we apply the described procedure to the remaining edges to construct
an additional path or cycle. We continue until no edges remain.
Observe that if both
σ
1
and
σ
2
are matchings in which all vertices in the graph are matched,
the procedure described above can only end in a cycle. As an example, consider the two matchings
found in Section
5.2.1
,
σ
1
={
σ
2
are
e
34
and
e
43
, and vertices 3 and 4 of the first schema are matched with vertices 4 and 3 of the
second schema, respectively. Performing the procedure on
(σ
1
\
σ
2
)
∪
(σ
2
\
σ
1
)
yields the alternating
cycle
e
11
,e
22
,e
34
,e
43
}
and
σ
2
={
e
11
,e
22
,e
33
,e
44
}
. The edges in
σ
1
\
e
43
,e
33
,e
34
,e
44
.
In this section, we describe an
O(
|
V
|
3
)
algorithm for finding the second-best matching. We
start by transforming the given graph
G(X,Y,E)
into a complete bipartite graph with sides of equal
size. This can be achieved by adding a set
U
of dummy vertices to the smaller side of the given graph
and placing an edge of zero weight between each pair of vertices that are not connected by an edge.
1
Let
G
(X
,Y
,E
)
be the resulting graph.
Let
σ
1
be the maximum weight matching in
G
. Assume without the loss of generality that
each vertex of
G
is matched in
σ
1
.Let
σ
be another matching in
G
such that each vertex of
G
is matched in
σ
. The edges in
σ
1
\
σ
∪
σ
\
σ
1
form a collection of alternating cycles. We use the
latter observation to reduce the problem of finding the maximum weight matching that differs from
σ
1
to the problem of finding the minimum weight path in a graph. We define the directed graph
D(V
D
,E
D
)
as follows:
V
D
=
V
E
D
=
E
2
where
E
1
={
(u, v)
|
(u, v)
∈
σ
1
,u
∈
X, v
∈
Y
}
E
1
∪
and
σ
1
,u
E
2
={
(v, u)
|
(u, v) /
∈
∈
X, v
∈
Y
}
.
We define the weight function
c
on the edges
E
D
as follows. For each
(u, v)
∈
E
1
, let
c(u, v)
=
(u, v)
. For each
(u, v)
(u, v)
.
Next, we state the algorithm for finding the second-best matching using alternating cycles.
For each edge
(u, v)
∈
E
2
, let
c(u, v)
=−
σ
1
, the algorithm constructs a minimum weight cycle in
D
containing the
edge
(u, v)
. Then it finds the minimum weight cycle
C
over all the cycles mentioned above. To
compute the second-best matching in
G
, the algorithm starts with
σ
1
∈
and replaces the edges from
σ
1
that appear on
C
by edges on
C
, which are not in
σ
1
.
Example 5.3
Figure
5.1
provides a pictorial illustration of
D(V
D
,E
D
)
. Edges of the best matching
are drawn as bold solid lines. The weights were computed from Table
3.2
using
c
. The minimum
weight paths from
v
2
to
u
1
for each
(u
1
,v
2
)
∈
σ
1
are presented in Table
5.2
, along with the associ-
ated cycle weights. The minimum weight cycle is
C
43
={
e
43
,e
33
,e
34
,e
44
}
, which is an alternating
cycle. After eliminating the edges of
C
43
∩
σ
1
from
σ
1
and including
C
43
\
C
43
∩
σ
1
={
e
34
,e
43
}
=
, one identifies the second-best matching
σ
2
{
e
33
,e
44
}
={
e
11
,e
22
,e
33
,e
44
}
.
1
Such a transformation requires a minor change in how we define edge weights to
:
E
→
.
