Branch decomposition techniques for discrete optimization<br/><br/>

Friday, November 3, 2006 - 4:30pm - 5:00pm
EE/CS 3-180
Illya Hicks (Texas A & M University)
This talk gives a general overview of an emerging technique for discrete
optimization that has footholds in mathematics, computer science, and
operations research: branch decompositions. Branch decompositions along
with its respective connectivity invariant, branchwidth, were first
introduced to aid in proving the Graph Minors Theorem, a well known
conjecture (Wagner's conjecture) in graph theory. The algorithmic
importance of branch decompositions for solving NP-hard problems modeled
on graphs was first realized by computer scientists. The dynamic
programming techniques utilizing branch decompositions, called branch
decomposition based algorithms, fall into a class of algorithms known as
fixed-parameter tractable algorithms and this talk will highlight the
computational effectiveness of these algorithms in a practical setting
for NP-hard problems such as the travelling salesman problem, general
minor containment, and the branchwidth problem.