MSc Thesis Defense by Henrik Bendt: Approximate Vertex-Label Distance Oracles – Københavns Universitet

MSc Thesis Defense by Henrik Bendt: Approximate Vertex-Label Distance Oracles

On 30 June at 4:00 pm, Henrik Bendt will defend his master's thesis.

Title

Approximate Vertex-Label Distance Oracles

Abstract

Given an undirected, non-negatively weighted graph G=(V,E) with n=|V| and m=|E|, where each vertex v in V is assigned a label from a set L of t labels, we show how to construct compact (4k-5)-stretch vertex-label approximate distance oracles improving on Chechik's O(m min{n^{k/(2k-1)},t}) preprocessing time bound for non-sparse graphs and large enough k, while preserving stretch, size and query time bounds. The improvements are achieved from three different applications of the technique used by Wulff-Nilsen in his improvement of the preprocessing time bound of Thorup-Zwick's distance oracles.

In addition, we also implement and experiment on these oracles to observe how they behave in practice.