Master Thesis presentation: "Spanner Islands and Spanner Paths"
Date: October 28, 2009 (Wednesday) at 10:15 to 11:00
Mikael Nilssons presents his Master Thesis "Spanner Islands and Spanner Paths".
Abstract:
In this Master Thesis the possibility to efficiently divide a graph into spanner islands is examined. Spanner islands are islands of the graph that fulfill the spanner condition, that the distance between two nodes via the edges in the graph cannot be too far, regulated by the stretch constant, compared to the Euclidian distance between them. In the resulting division the least number of nodes connecting to other islands is sought-after. Different heuristics are evaluated with the conclusion that for dense graphs a heuristic using MAX-FLOW to divide problematic nodes gives the best result whereas for sparse graphs a heuristic using the single-link clustering method performs best...
Room: E:2405
Last modified Dec 9, 2011 12:57 pm
020