CMU-CS-17-120
Computer Science Department
School of Computer Science, Carnegie Mellon University


CMU-CS-17-120

Exponential Start Time Clustering and its Applications in Spectrual Graph Theory

Shen Chen Xu

August 2017

Ph.D. Thesis

CMU-CS-17-120.pdf


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.

A common goal we strive for in the design of these algorithms is to achieve complexities that are nearly linear in the input size in order to be scalable to the ever-growing amount of data and problem sizes in this day and age.

112 pages

Thesis Committee:
Gary L. Miller (Chair)
Bernhard Haeupler
Daniel D.K. Sleator
Noel J. Walkington
Ioannis Koutsis (University of Puerto Rico)

Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science


Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu