What's on in Computing Science?

Date: Tuesday, 13 March, 2012
Time: 16:00
Location: Sir Alwyn Williams Building, 422 Seminar Room
[FATA talk] An introduction to Binary Decision Diagrams (BDDs)
Alice Miller
A BDD [Bryant, 1986] is an efficient, compressed, canonical data structure for the representation of sets and relations. They are described by Donald Knuth as “one of the only really fundamental data structures that came out in the last 25 years”. BDDs are used by many of us in FATA to do model checking (with Prism), whether we are aware of the fact or not! Some operations are super-efficient when applied to BDDs, and there are packages which will perform these operations for us (we just have to express our problem in terms of these operations). In this talk I will focus on the use of BDDs for graph manipulation, e.g. finding the neighbourhood of a (set of) node(s) in a graph. Specifically I hope to, at least in part, address Gethin’s question in Patrick’s FATA talk last week: can the use of BDDs make maximal clique generation more efficient?

Contact: Dr Oana Andrei (oana.andrei@glasgow.ac.uk)

Add to my calendar