Abstract
This talk gives an introduction to the subfield of algorithm theory that
studies graph reachability and distance problems. The talk is geared
towards researchers not working in algorithms, e.g. researchers in
database theory. We discuss the problems single-source reachability,
all-pairs reachability, single-source shortest paths, and all-pairs
shortest paths on undirected and directed graphs with respect to various
parameters, as well as relaxations to approximation algorithms.