SCS Undergraduate Thesis Topics

2014-2015 | ||

Student | Advisor | Thesis Topic |

Terence An | Guy Blelloch | Fast Approximation of Minimum 2-Hop Covers on Trees |

Distance queries on graphs is a fundamental problem for numerous
real-world applications. Constant queries can be done with an APSP
algorithm but that requires storing every pair of distances in
Ω(n ^{2}) space, whereas dynamically resolving distances requires
O(m + n log(n)) time on m-edge n-vertex graphs.
An algorithm that stores fewer precomputed values and reduces dynamic query time is the
2-hop labeling scheme where every vertex stores its distance (called a
label) to a subset of the other vertices such that for any pair of vertices, they both have their distance to at least one vertex on their shortest
path. The problem we study is minimizing the number of labels needed
to correctly query distances. There is now a log(n) approximation
algorithm for m-edge n-vertex graphs that runs in O(mn ^{3})
time for this. We demonstrate this problem is NP-Complete, and we present the currently fastest algorithm which gives a log(n) approximation on n-vertex trees which runs in
Θ(nlog(n)). We also prove that this the optimal runtime for any correct tree-labeling algorithm.

Close this window