Biology Reference
In-Depth Information
Fig. 1.5. In case (C1), adding the edge
{v,w}
does not need to be considered. Here,
G
is the given
graph and
G
is a clustering solution of
G
that adds the edge
{v, w}
. The dashed lines denote edges
being deleted to transform
G
into
G
, and the bold lines denote edges being added. Observe that the
drawing only shows that parts of the graphs (in particular, edges) which are relevant for our argument.
Here, we omitted possible vertices which are neighbors of
w
in
G
but not in
G
:
G
.
they would only increase the cost of transformation
G
→
G
G
,that
In summary, the cost of
G
→
is not higher than the cost of
G
→
is, we do not need more edge additions and deletions to obtain
G
from
G
than to
obtain
G
from
G
.
As a consequence of Lemma 1.1, the search tree only has to branch into two
instead of three subcases in case (C1). Making use of the markers “permanent”
and “forbidden,” the standard branching into three subcases can also be avoided
in cases (C2) and (C3). Each of these cases, however, requires specific considera-
tions [34] which have to be omitted here.
Besides a search tree strategy for C
LUSTER
E
DITING
, also data reductions
yielding problem kernels are known for this problem. The first result was a prob-
lem kernel with
O
(
k
2
) vertices [34] and this has recently been improved to a prob-
lem kernel with only
O
(
k
) vertices [28, 38]. For a practical solving algorithm, the
search tree has to be combined with the kernelization [23, 34, 59]. By splitting up
cases (C2) and (C3) further using a computer, we arrive at the following theorem.
Theorem 1.4 (Gramm et al. [33], Protti et al. [63]).
C
LUSTER
E
DITING
can
be solved in
O
(1
.
92
k
+
n
+
m
)
time.
For a recent implementation of the above strategy, experiments indicated that
the fixed-parameter approach outperforms a solution based on linear programming
and appears to be of practical use [23]. The implementation can solve certain
synthetic instances with
n
= 100 and 40 edit operations within an hour.
There are several problems closely related to C
LUSTER
E
DITING
that deserve
similar studies. Among these are the more general C
ORRELATION
C
LUSTERING
Search WWH ::
Custom Search