Abstract
Algorithms for network problems play an increasingly important
role in modern society. The graph structure of a network is an abstract
and very useful representation that allows classical graph algorithms,
such as Dijkstra and Bellman-Ford, to be applied. Real-life networks
often have additional structural properties that can be exploited. For
instance, a road network or a wire layout on a microchip is typically
(near-)planar and distances in the network are often defined w.r.t. the
Euclidean or the rectilinear metric. Specialized algorithms that take
advantage of such properties are often orders of magnitude faster than
the corresponding algorithms for general graphs.
The first and main part of this thesis focuses on the development of
efficient planar graph algorithms. The most important contributions
include a faster single-source shortest path algorithm, a distance oracle
with subquadratic preprocessing time, an O(n log n) time algorithm
for the replacement paths problem, and a min st-cut oracle with nearlinear
preprocessing time. We also give improved time bounds for
computing various graph invariants such as diameter and girth.
In the second part, we consider stretch factor problems for geometric
graphs and graphs embedded in metric spaces. Roughly speaking,
the stretch factor is a real value expressing how well a (geo-)metric
graph approximates the underlying complete graph w.r.t. distances.
We give improved algorithms for computing the stretch factor of a
given graph and for augmenting a graph with new edges while minimizing
stretch factor.
The third and final part of the thesis deals with the Steiner tree
problem in the plane equipped with a weighted fixed orientation metric.
Here, we give an improved theoretical analysis of the strength
of pruning techniques applied by many Steiner tree algorithms. We
also present an algorithm that computes a so called Steiner hull, a
structure that may help in the computation of a Steiner minimal tree.
| Original language | English |
|---|
| Publisher | Museum Tusculanum |
|---|---|
| Number of pages | 230 |
| Publication status | Published - 2010 |