All reports by Author Jesper Torp Kristensen:

__
TR06-004
| 6th January 2006
__

Jesper Torp Kristensen, Peter Bro Miltersen#### Finding small OBDDs for incompletely specified truth tables is hard

Jesper Torp Kristensen, Peter Bro Miltersen

We present an efficient reduction mapping undirected graphs

G with n = 2^k vertices for integers k

to tables of partially specified Boolean functions

g: {0,1}^(4k+1) -> {0,1,*} so that for any integer m,

G has a vertex colouring using m colours if and only if g ...
more >>>