Department of Mathematics and Computer Science |

In analyzing algorithms, it is crucial to have a well-defined theoretical tool
for predicting how well algorithms will do in practice.
The standard measure for the quality of on-line algorithms is the
*competitive ratio*, which has existed for more than
twenty years.

However, it is well recognized that there are many cases where the results the competitive ratio gives are unsatisfactory as predictors of algorithms' performances. One of these is the paging problem where the competitive ratio does not separate algorithms that are known to perform very differently in practice. Hence, there have been many attempts to provide supplements or alternatives to the competitive ratio.

One such new measure for the quality of on-line algorithms,
the *relative worst order ratio*, was proposed
by Boyar and Favrholdt.
In contrast to most earlier proposals, the relative worst order ratio has
already been applied to several problems of different nature, giving results
which are superior to those obtained with competitive analysis.
Recent work announced at an
international meeting through four presentations by
Boyar, Favrholdt, Larsen, and Ehmsen (one of the group's Ph.D. students)
shows its superiority to some other measures as well. There was
great interest in comparisons
of the many proposed supplements and alternatives to the
competitive ratio, as presented by the SDU group as well as
other invited speakers.
In the past, most researchers compared new quality measures to the
competitive ratio only; comparisons to other quality measures are
only very recently starting to happen.
More full comparisons of the ability of different quality measures
to predict the behavior of online algorithms for online problems are needed.
This will pave the way for drawing general conclusions about which
measures are most useful in which situations and how these can be characterized.

Both of the books co-authored by Bang-Jensen and Toft (*Digraphs: Theory,
Algorithms and Applications*, by J. Bang-Jensen and G. Gutin, and
*Graph Coloring Problems*, by T.R. Jensen and B. Toft)
contain a large number of open problems and
conjectures many of which could form the starting point of a Ph.D.
thesis. One such topic is deciding the existence of orientations of
undirected graphs (the assignment of directions to the edges of the
undirected graph, making it directed) such that certain parameters are met
(such as connectivity or containment/avoidance of certain
substructures). These problems very often
have both theoretical (structural results, which are often the key step in
developing efficient algorithms) and algorithmic (determining the existence
of orientations with the desired properties or finding the desired
orientations) subproblems of independent interest. Graph coloring
(assigning colors to the vertices so that no two adjacent vertices have the
same color) is one of the most popular graph theoretical topics within
computer science and operations research because of the many challenging
open problems (of which many are described in Toft's book) and because
many real-life problems (in particular timetabling and scheduling problems,
for example how to schedule without, or with only few, waiting periods.)
can be formulated as graph coloring problems. Colorings of undirected
graphs is also closely related to orientations of graphs and
there are a number of interesting open problems dealing with this
connection between a digraph and the chromatic number of its underlying
undirected graph. Studying these connections would be a very interesting
Ph.D. project.

Another topic for a project is to study problems for directed graphs where we are looking for stuctures, only part of which need to adhere with the orientation of the arcs in the digraph. One such example is the question of deciding when a digraph has an out-branching whose (arc)-deletion leaves a connected graph (in the undirected sense).

In recent studies the group has, for example, applied gene cluster constraints to develop algorithms that lead to tremendous speedups when solving core problems for phylogenetic reconstruction. Algorithms based on these methods were recently applied to comprehensively analyze the phylogenetics of all known echinoderms and to identify undocumented events in mitogenomes. In these studies also so-called tandem duplication random loss (TDRL) operations for genomic rearrangement were considered, as there is strong support for this operation in biology. A TDRL duplicates a contiguous segment of genes, followed by the loss of one copy of each of the duplicated genes. This operation is even considered as ``being the most important rearrangement operation in vertebrates''.

The group has also strong expertise in reconstruction of the
co-phylogenetic history of species.
Co-evolutionary systems, such as hosts and their parasites or plants
and insects that feed or breed on these plants, are a commonly used
model systems for evolutionary studies. The core problem is to
reconstruct the common history from the known phylogenies and the
current relationships (for an overview see, for example, "Traversing
the tangle: algorithms and applications for
cophylogenetic studies", in *Journal of Biomedical Informatics*,
by M.A. Charleston and S.L. Perkins). The
current relations between the species from both groups (for
example, which
parasite lives on which host species) are often known from field
studies or laboratory experiments. However, using relevant biological
information such as divergence timing of the phylogenetic trees or
geographic information of the species also from an algorithmic
perspective has only rarely been investigated. The inclusion of such
information will certainly open the door for very promising
Ph.D. projects.

Due to the expert knowledge of the research group in the fields of computational biology, Ph.D. students will receive an education that emphasizes interdisciplinary and internationality. Several scientific meetings in the area of information technology and life sciences were organized by the research group already, where especially young academics were encouraged to participate (e.g. German Workshop on Artificial Life 2008 GWAL-8; Swarm Intelligence and Computational Biology at the IEEE Swarm Intelligence Symposium 2007; Molecular Docking, Complexity, and Optimization MDCO-07).