University of Cambridge > Talks.cam > Logic and Semantics for Dummies > Tree decomposition of graphs

Tree decomposition of graphs

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity