English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Thesis

NP-hard Networking Problems : Exact and Approximate Algorithms

MPS-Authors
/persons/resource/persons45109

Naujoks,  Rouven
Algorithms and Complexity, MPI for Informatics, Max Planck Society;
International Max Planck Research School, MPI for Informatics, Max Planck Society;

Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Naujoks, R. (2008). NP-hard Networking Problems: Exact and Approximate Algorithms. PhD Thesis, Universität des Saarlandes, Saarbrücken. doi:10.22028/D291-26100.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-1A84-2
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.