Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 01, 2013, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Torsten Mütze
A binary decision diagram, BDD for short, is a data structure to represent a boolean function. In this talk I will discuss the amazing possibilities BDDs offer to solve the three most fundamental combinatorial problems:
- counting all objects from a family X
- generating uniformly random elements from X
- computing weighted maxima/minima over all elements in X
Here X is some family of combinatorial objects, e.g. all independent sets, matchings, colorings, spanning trees or Hamilton paths/cycles of a graph (choose your favourite). Based on material from [D. Knuth, The Art of Computer Programming, Vol. 4], I will introduce the main techniques to do combinatorics with BDDs and illustrate them with various examples.
Personal note: I got to know BDDs in the context of Boolean circuit verification, and when I learned about their applications in combinatorics from Knuth's book, I realized that this topic deserves to be much better known.
Automatic MiSe System Software Version 1.4803M | admin login