Albion College
Mathematics and Computer Science
COLLOQUIUM
Treewidth, Algorithm Design and Computational Complexity: How We Can Exploit Problem Structure to CreateFaster Algorithms
Harold Connamacher

Assistant Professor

Mathematics and Computer Science

Albion College

Treewidth is a fundamental property of a graphs. The treewidth property was defined by Neil Robertson and Paul Seymour in the late 1970's. Originally used to answer Wagner's Conjecture on graph minors, in the decades that followed there was an explosion of research using treewidth to study other graph structures, computational complexity, and algorithm design. New algorithms based on treewidth have been used in many areas of computer science including databases and artificial intelligence. This talk will introduce fundamental concepts in algorithms, computational complexity, and discrete mathematics.It will then introduce treewidth and show how we can create fast algorithms for intractable problems when the underlying graph of the problem has small treewidth.
3:10 PM
All are welcome!
Palenske 227
October 2, 2008