BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Logic and Semantics for Dummies
SUMMARY:Tree decomposition of graphs - Bjarki Holm (Univer
sity of Cambridge)
DTSTART;TZID=Europe/London:20080314T110000
DTEND;TZID=Europe/London:20080314T120000
UID:TALK11155AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/11155
DESCRIPTION:Tree-width is a property that measures the similar
ity of a graph with a tree. Recent years have seen
many important applications of tree-width in algo
rithm design and complexity theory\, as it turns o
ut that many NP-hard decision and optimisation pro
blems are solvable in polynomial time when restric
ted 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 a
re some nice combinatorial games that allow us to
establish upper bounds on tree-width on restricted
classes of graphs.\n\nAlso\, 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 langua
ges. 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
CONTACT:Alexander Gurney
END:VEVENT
END:VCALENDAR