In this talk, a survey will be given of recent work to compute the treewidth of graphs. For several applications, it is desirable to have fast methods to compute the treewidth of a given graph, and to build a tree decomposition of optimal, or close to optimal treewidth. We will look at several types of algorithms for this problem: exact algorithms, heuristics, preprocessing. The talk will discuss different algorithmic techniques, their impact and usefullness in actual implementations, and the graph theory behind the algorithms and programs.
The Tree of Life initiative -- to reconstruct the evolutionary history of all organisms -- is the computational grand challenge of evolutionary biology. Current methods are limited to problems several orders of magnitude smaller and also fail to provide sufficient accuracy at the high end of their range. The NSF-funded Cyberinfrastructure for Phylogenetic Research (CIPRes) project funds about 40 investigators from 13 institutions, to help develop the computational infrastructure for evolutionary biologists so that they can analyze large datasets. In this talk, I will discuss several algorithmic and software projects within CIPRES, including