Thesis (Server


Doctoral dissertation | @PhdThesis{NaujoksPhD, ... | Doktorarbeit

Naujoks, Rouven

NP-hard Networking Problems - Exact and Approximate Algorithms

Universität des Saarlandes, December, 2008

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.

networks, Steiner trees, Hamming metric, exact algorithms, approximate algorithms, wireless communication
Download File(s):
Prof. Dr. Kurt Mehlhorn
Prof. Dr. Ernst Althaus
Prof. Dr. Joachim Weickert
Max-Planck-Institut für Informatik
Algorithms and Complexity Group
experts only
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:
AUTHOR = {Naujoks, Rouven},
TITLE = {NP-hard Networking Problems - Exact and Approximate Algorithms},
SCHOOL = {Universit{\"a}t des Saarlandes},
YEAR = {2008},
TYPE = {Doctoral dissertation}
MONTH = {December},

Entry last modified by Rouven Naujoks, 03/03/2009
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Rouven Naujoks
02/12/2009 12:55:25 PM

Rouven Naujoks
Rouven Naujoks

Edit Date
02/12/2009 01:10:16 PM
02/12/2009 12:55:25 PM