Tree decomposition of graphs

Add to your list(s) Download to your calendar using vCal

• Bjarki Holm (University of Cambridge)
• Friday 14 March 2008, 11:00-12:00
• GS15, Computer Laboratory.

If you have a question about this talk, please contact Alexander Gurney.

Tree-width is a property that measures the similarity of a graph with a tree. Recent years have seen many important applications of tree-width in algorithm design and complexity theory, as it turns out that many NP-hard decision and optimisation problems are solvable in polynomial time when restricted to graphs whose tree-width is bounded by some constant.

While it is hard to compute the tree-width of an arbitrary graph, it turns out there are some nice combinatorial games that allow us to establish upper bounds on tree-width on restricted classes of graphs.

Also, people have recently discovered some novel applications of tree-width to the study of Java module systems, metarouting algorithms, categorical type theory, operational semantics, and concurrency in programming languages. So if you are working in one of those areas, you better make sure you don’t miss this talk.

This talk is part of the Logic and Semantics for Dummies series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• GS15, Computer Laboratory
• Logic and Semantics for Dummies

Note that ex-directory lists are not shown.