CMU-CS-17-120Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-17-120
Shen Chen Xu August 2017 Ph.D. Thesis
Keywords:
Spectral Graph Theory, Exponential Start Time Clustering, Graph Spanners,
Spectral Graph Sparsification, Low Stretch Tree Embeddings, Hopsets
Recent progress on a number of combinatorial and numerical problems benefited from combining ideas and techniques from both fields to design faster and more powerful algorithms. A prime example is the field of spectral graph theory, which involves the interplay between combinatorial graph algorithms with numerical linear algebra. This led to the first nearly linear time solvers for graph Laplacians as well as symmetric and diagonally dominant (SDD) linear systems. In this thesis we present several combinatorial algorithms that allow us to tap into spectral properties of graphs. In particular, we present - An improved parallel algorithm for low diameter decomposition via exponential shifts.
- A parallel algorithm for graph spanners with near optimal stretch trade-offs and its application to spectral graph sparsification.
- Improved low stretch tree embeddings that are suitable for fast graph Laplacian solvers.
- Work efficient parallel algorithms for hopset and approximate shortest path.
112 pages
Frank Pfenning, Head, Computer Science Department
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |