Department of Computer Science DIKU > News > News 2010 > Christian Wulff-Nilsen...
15. juni 2010
Christian Wulff-Nilsen is now PhD in computer science
On basis of the defence of his PhD-thesis Algorithms for Planar Graphs and Graphs in Metric Spaces Christian Wulff-Nilsen on 15th June 2010 received the PhD degree in computer science.
During his PhD study Christian has been a frequent submitter of scientific articles and conference papers and the thesis thus crowned these achievements and results, describing i.a. how algorithms can be used to find the shortest path in a GPS system.
Assessment Committee:
Chairman: Associate Professor Pawel Winter (DIKU, University of Copenhagen)
Dr. Leah Eppstein, Department of Mathematics, University of Haifa
Professor Bengt J. Nilsson, Malmö University
Academic supervisor:
Associate Professor and head of department Martin Zachariasen (DIKU, University of Copenhagen)
DIKU congratulates Christian with the degree.
A few highlights from the defence
 From left: Welcome and introduction by Associate professor Pawel Winter. Introduction to the thesis by Christian Wulff-Nielsen, The assessment committee and the academic supervisor pay full attention |
 |
 |
 |
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 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.