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