  In this thesis, we present new techniques to deal with fundamental
algorithmic graph problems where graphs are directed and partially dynamic,
i.e. undergo either a sequence of edge insertions or deletions:
  - Single-Source Reachability (SSR),
  - Strongly-Connected Components (SCCs), and
  - Single-Source Shortest Paths (SSSP).
  These problems have recently received an extraordinary amount of attention
due to their role as subproblems in various more complex and notoriously hard
graph problems, especially to compute flows, bipartite matchings and cuts.
  Our techniques lead to the first near-optimal data structures for these
problems in various different settings. Letting $n$ denote the number of
vertices in the graph and by $m$ the maximum number of edges in any version of
the graph, we obtain
  - the first randomized data structure to maintain SSR and SCCs in
near-optimal total update time $\tilde{O}(m)$ in a graph undergoing edge
deletions.
  - the first randomized data structure to maintain SSSP in partially dynamic
graphs in total update time $\tilde{O}(n^2)$ which is near-optimal in dense
graphs.
  - the first deterministic data structures for SSR and SCC for graphs
undergoing edge deletions, and for SSSP in partially dynamic graphs that
improve upon the $O(mn)$ total update time by Even and Shiloach from 1981 that
is often considered to be a fundamental barrier.
