NP-hard networking problems : exact and approximate algorithms

Abstract

An important class of problems that occur in different fields of research such 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. Additionaly, these networks should satisfy certain properties and minimize a certain cost function. In this thesis, we discuss such NP-hard networking problems in two parts. First, we mainly deal with the so-called Steiner minimum tree problem in Hamming metric. The computation of such trees has become 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 has been considered to be the fastest for the last 25 years. Further, we propose an extended model to cope with the case in which the ancestral relationships are best described by a non-tree structure. Finally, 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. We show how approximate solutions can be found for these problems.

In verschiedenen wissenschaftlichen Disziplinen, wie der Biologie, der Linguistik und dem Entwurf kabelloser Kommunikationsnetzwerke, wird man mit der Konstruktion von Verbindungsnetzwerken über einer gegebenen Menge von Objekten konfrontiert. Diese Netzwerke sollen bestimmte Eigenschaften erfüllen und gleichzeitig eine gegebene Kostenfunktion minimieren. In dieser Arbeit werden NP-schwere Netzwerkprobleme dieser Art behandelt. Die Arbeit untergliedert sich in zwei Teile. Im ersten Teil beschäftigen wir uns hauptsächlich mit dem so genannten Steinerbaumproblem in der Hamming-Metrik. Die Berechnung solcher Bäume hat sich als eines der Hauptwerkzeuge in der Rekonstruktion abstammungsgeschichtlicher Beziehungen zwischen Spezien herausgestellt. Wir geben einen neuen, exakten Algorithmus, welcher der Branch-and-Bound-Methode von Hendy und Penny deutlich überlegen ist. Diese galt in den letzten 25 Jahren als die schnellste Methode zur Berechnung solcher Bäume. Des Weiteren stellen wir ein erweitertes Modell vor, welches die Fälle behandelt, in denen die abstammungsgeschichtlichen Beziehungen bestmöglich durch eine nicht baumartige Struktur beschrieben wird. Im zweiten Teil beschäftigen wir uns mit verschiedenen Problemen, wie sie bei dem Entwurf kabelloser Ad-hoc-Netzwerke auftreten: Unter denjenigen Kommunikationsstrukturen, die bestimmte Kommunikationsarten zulassen, versucht man diejenige zu finden, welche die Stromaufnahme des Netzwerkes minimiert. Wir zeigen, wie für diese Probleme approximative Lösungen gefunden werden können.