DATE: Oct 16, 2020 (Friday)
TIME: 11:45 am EST

SPEAKER: David Trench

TITLE: Algorithms for Massive and Changing Graphs

ABSTRACT: Some graph data sets such as social networks can be too large to fit in main memory, invalidating the typical assumption that an algorithm has random access to its input. For computation on massive graph data sets we consider the dynamic streaming graph model: given an input graph defined by a stream of edge insertions and deletions, our goal is to approximate properties of this graph using space that is sublinear in the size of the stream.  I will present algorithms for computing connectivity and vertex connectivity in graph streams, and pose a problem on how to compute connectivity on graphs whose edges exist at some times and not others.