PhD Dissertation Defense: Katina Russell

Title: Algorithms for Large Scale Graphs

Constructing efficient algorithms for graph problems is a fundamental problem in computer science theory. This dissertation studies algorithms for large scale graphs and focuses on directed graph problems. We consider directed graph problems in several models of computation with the goal of improving performance for large scale graphs. The models of computation include the external memory model, the work-span model for parallel algorithms, and the asymmetric RAM model. The hypothesis is there exist provably efficient algorithms for directed graphs problems for large scale graphs.

The following results are presented. First, an I/O-efficient algorithm for topologically sorting a directed acyclic graph, as well as an algorithm for identifying and topologically sorting the strongly connected components of a directed graph. Both algorithms cost O(E/B log_{M/B} V/B * log^4 V) I/Os and are the first I/O-efficient algorithms for these problems for sparse graphs. Second, this work shows an algorithm for constructing a (1 + ε) directed hopset of size Õ(n) in Õ(m) work and n^{1/2 + o(1)} hop-bound. Our parallel version of the algorithm can be used to solve parallel approximate single-source shortest paths in Õ(m) work and n^{1/2+o(1)} span. Next, we show a parallel algorithm for distance-limited shortest paths on directed acyclic graphs with 0 and -1 edge weights. The algorithm computes single-source shortest paths for nodes with distance at least -L, and runs in Õ(m) work and O(L^{1/2}n^{1/2+o(1)}) span. Finally we give write-efficient algorithms for breadth-first search, depth-first search and strongly connected components. The standard RAM algorithms for these problems write the solution for each node. Instead we write only a subset of the nodes to save writes, at the expense of more reads to answer a query. Our result is sublinear size data structures that can answer queries for each of the three graph problems.