15. juni 2010

Christian Wulff-Nilsen ny PhD i computer science

Med afhandlingen Algorithms for Planar Graphs and Graphs in Metric Spaces modtog  Christian Wulff-Nilsen den 15. juni 2010 PhD-graden i datalogi.

Christian har som Ph.d.-studerende været flittig formidler i form af videnskabelige artikler og konferencepapers og ph.d.-graden er således kronen på værket af en lang perlerække af datalogiske forskningsresultater. Denne afhandling handler bl.a. om, hvordan algoritmer kan udregne den korteste rute i GPS-systemer.


Formand: Lektor Pawel Winter (DIKU, University of Copenhagen)
Dr. Leah Eppstein, Department of Mathematics, University of Haifa
Professor Bengt J. Nilsson, Malmö University


Lektor og institutleder Martin Zachariasen (DIKU, University of Copenhagen)

DIKU ønsker Christian tillykke med titlen.

Et par billeder fra præsentationen.

Øverst fra venstre: Lektor Pawel Winter byder velkommen. Introduktion til afhandlingen ved Chr. Wulff-Nielsen, Opponenterne og vejlederen lytter, overblik over afhandlingen



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 near-linear 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.

For an electronic copy of the thesis, please contact Jette Møller, jettegm@diku.dk, + 45 35 32 14 57.