Biology Reference
In-Depth Information
exist size-
o
(3
k
) search trees for
enumerating
all solutions to a given instance of
C
LUSTER
E
DITING
[20].
The basic approach to obtain the improved search trees for C
LUSTER
E
DIT
-
ING
is to do a case distinction, where we provide for every possible situation ad-
ditional branching steps. The analysis of successive branching steps, then, yields
a better worst-case bound on the search tree size. To this end, we make use of two
annotations for unordered vertex pairs:
“
permanent
”: In this case,
{
u,v
}∈
E
and it is not allowed to delete
{
u,v
}
;
“
forbidden
”: In this case,
{
u,v
}
∈
/
E
anditisnotallowedtoadd
{
u,v
}
.
{
u,v
}
Clearly, if an edge
is deleted, then the vertex pair is made
forbidden
.Ifan
edge
is added, then the vertex pair is made
permanent
.
We distinguish three main situations that may apply when considering the
conflict triple
{
u,v
}
{
u,v,w
}
:
(C1) Vertices
v
and
w
do not share a common neighbor, that is,
∀
x
∈
V,x
=
u
:
E
.
(C2) Vertices
v
and
w
have a common neighbor
x
{
v,x
} ∈
E
or
{
w,x
} ∈
=
u
and
{
u,x
}∈
E
.
(C3) Vertices
v
and
w
have a common neighbor
x
=
u
and
{
u,x
}
∈
/
E
.
Regarding case (C1), the following lemma shows that a branching into two sub-
cases suffices.
Lemma 1.1.
Givenagraph
G
=(
V,E
)
, a nonnegative integer
k
, and a con-
flict triple
u,v,w
∈
V
of vertices that satisfy case (C1) from above, adding the
edge
{
v,w
}
cannot yield a better solution than deleting one of the edges
{
u,v
}
or
{
u,w
}
.
Consider a clustering solution
G
for
G
wherewedidadd
Proof.
(see
Fig. 1.5 for an example). We use
N
G∩G
(
v
) to denote the set of vertices that
are neighbors of
v
in
G
and in
G
.
{
v,w
}
Without loss of generality, assume that
. We then construct a new graph
G
from
G
by
deleting all edges adjacent to
w
. It is clear that
G
is also a clustering solution
for
G
. We compare the cost of the transformation
G
|
N
G∩G
(
w
)
|≤|
N
G∩G
(
v
)
|
G
to that of the transfor-
→
G
:
mation
G
→
•−
1 for not adding
{v,w}
,
•
+1 for deleting
{
u,w
}
,
•−|
N
G∩G
(
v
)
|
for not adding all edges
{
w,x
}
,x
∈
N
G∩G
(
v
),
•
+
|
N
G∩G
(
w
)
|
for deleting all edges
{
w,x
}
,x
∈
N
G∩G
(
w
).
Search WWH ::
Custom Search