Biology Reference
In-Depth Information
problems and problems on weighted graphs therefore usually requires
some additional work to be done.
(4) Exponential memory consumption usually turns out to be more harmful
in practice than exponential time, especially in enumerative tasks. Using
memory-saving techniques generally pays off, even if this means some
decrease in time efficiency.
Data Reductions and Kernelizations
(1) One should always start by designing data reduction rules because these
are helpful in combination with basically any algorithmic technique that
is subsequently applied.
(2) The
order
of applying data reduction rules can significantly influence
the practical effectiveness and efficiency of the overall data reduction.
Experimental work is important to find good orderings.
(3) Even if a data reduction has no provable performance guarantee, it can
still turn out to be very effective in practice.
Depth-Bounded Search Trees
(1) The branching in a search tree can produce new opportunities for data
reduction. Therefore, data reductions should be applied repeatedly dur-
ing the course of the whole algorithm and not only as a preprocessing
step [59]. To achieve maximum efficiency, the exact frequency of apply-
ing data reductions may require some tuning.
(2) Search tree algorithms can be parallelized rather easily.
(3) Complicated case distinctions for the branching should be avoided when
a simpler search strategy is available that yields almost the same worst-
case running time bounds. The simpler strategy usually turns out to be
faster.
1.4.2.
Challenges
While there has been substantial work on fixed-parameter algorithms for cluster-
ing problems and several examples show the potential of this approach, the field
is still quite young, and there remain a couple of challenges for future research:
•
The C
LIQUE
model is often too restricted in applications; one would
rather prefer a notion of “dense subgraph” (e. g., Ref. 10, 43, 73). Except
Search WWH ::
Custom Search