Graphs have been widely utilized in network design and other applications. A natural question is, can we keep as few edges of the original graph as possible, but still make sure that the vertices are connected within certain distance constraints.
In this thesis, we will consider different versions of graph compression problems, including graph spanners, approximate distance oracles, and Steiner networks. Since these problems are all \(\mathrm{NP}\)-hard problems, we will mostly focus on designing approximation algorithms and proving inapproximability results.
Speaker Biography
I am a Ph.D. candidate advised by Professor Michael Dinitz in the Department of Computer Science at Johns Hopkins University. My research focuses on approximation algorithms and graph algorithms. I received a B.S. in Mathematics from Tsinghua University in 2014.