Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF D1 Publications :: Thesis :: Naujoks, Rouven

MPI-INF D1 Publications
Show all entries of:this year (2020)last year (2019)two years ago (2018)Open in Notes
Action:login to update

Thesis - Doctoral dissertation | @PhdThesis | Doktorarbeit

Author(s)*:Naujoks, Rouven
BibTeX citekey*:NaujoksPhD

Title, School
Title*:NP-hard Networking Problems - Exact and Approximate Algorithms
School:Universität des Saarlandes
Type of Thesis*:Doctoral dissertation

Note, Abstract, Copyright
LaTeX 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.
Keywords:networks, Steiner trees, Hamming metric, exact algorithms, approximate algorithms, wireless communication
Download Access Level:Public
Download File(s):

Referees, Status, Dates
1. Referee:Prof. Dr. Kurt Mehlhorn
2. Referee:Prof. Dr. Ernst Althaus
Date Kolloquium:22 December 2008
Chair Kolloquium:Prof. Dr. Joachim Weickert

MPG Unit:Max-Planck-Institut für Informatik
MPG Subunit:Algorithms and Complexity Group
Audience:experts only
Appearance: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