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.