Speaker: Laura Sheppardson (University of Mississippi)

Title: Exploiting structural aspects of graph models

Abstract: Graphs are commonly used to model problems in diverse fields, including predictive chemistry,  circuit design, transportation planning, gene clustering, and dynamical systems.  In this talk  we will review several surprisingly powerful tools used in proving graph theoretic results.  These include some standard reductions based on graph connectivity as well as tree decomposition.  We show how these tools can be used to build constructive algorithms, drawing on recent results on long cycles and disjoint paths for examples.  We will also touch on how specific structures can assure upper bounds on the complexity of many graph algorithms.