Title: | Treewidth, Algorithm Design and Computational Complexity: How We Can Exploit Problem Structure to CreateFaster Algorithms |

Speaker: | Harold Connamacher Assistant Professor Mathematics and Computer Science Albion College Albion, Michigan, USA |

Abstract: | 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. |

Location: | Palenske 227 |

Date: | 10/2/2008 |

Time: | 3:10 PM |

@abstract{MCS:Colloquium:HaroldConnamacher:2008:10:2, author = "{Harold Connamacher}", title = "{Treewidth, Algorithm Design and Computational Complexity: How We Can Exploit Problem Structure to CreateFaster Algorithms}", address = "{Albion College Mathematics and Computer Science Colloquium}", month = "{2 October}", year = "{2008}" }