Item

Abstract

An important class of problems that occur in different fields of research as
biology, linguistics or in the design of wireless communication networks deal
with the problem of finding an interconnection of a given set of objects. In
the first one, we mainly deal with the so called Steiner minimum tree problem
in Hamming metric. The computation of such trees has turned out to be a key
tool for the reconstruction of the ancestral relationships of species. We give
a new exact algorithm that clearly outperforms the branch and bound based
method of Hendy and Penny which was considered to be the fastest for the last
$25$ years. Additionally, we propose an extended model that copes with the case
in which the ancestral relationships are best described by a non-tree
structure. In the last part, we deal with several problems occurring in the
design of wireless ad-hoc networks: While minimizing the total power
consumption of a wireless communication network one wants to establish a
messaging structure such that certain communication tasks can be performed. For
these problems we show how approximate solutions can be found.