BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Tree decomposition of graphs - Bjarki Holm (University of Cambridg
 e)
DTSTART:20080314T110000Z
DTEND:20080314T120000Z
UID:TALK11155@talks.cam.ac.uk
CONTACT:Alexander Gurney
DESCRIPTION:Tree-width is a property that measures the similarity of a gra
 ph with a tree. Recent years have seen many important applications of tree
 -width in algorithm design and complexity theory\, as it turns out that ma
 ny NP-hard decision and optimisation problems are solvable in polynomial t
 ime when restricted to graphs whose tree-width is bounded by some constant
 .\n\nWhile 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 establ
 ish upper bounds on tree-width on restricted classes of graphs.\n\nAlso\, 
 people have recently discovered some novel applications of tree-width to t
 he study of Java module systems\, metarouting algorithms\, categorical typ
 e theory\, operational semantics\, and concurrency in programming language
 s. So if you are working in one of those areas\, you better make sure you 
 don't miss this talk.\n
LOCATION:GS15\, Computer Laboratory
END:VEVENT
END:VCALENDAR