Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algorithm to compute join in zero suppressed binary decision diagram

What is the algorithm to compute the join of two zero suppressed binary decision diagrams?

I've searched for it for hours now, I just can't find it. It's not in Knuth's book either, as far as I can find, though it does give a definition of the result.

I would prefer not to have to wade through any specific implementation; I find the implementation details very distracting.


The join of ZDDs f and g is { a ∪ b | a ∈ f and b ∈ g }

like image 234
harold Avatar asked Aug 30 '11 11:08

harold


1 Answers

In my copy of The Art of Computer Programming, Volume 4A this exact question is posed as Exercise 205 in section 7.1.4. It's related to the two previous questions, but the answers to all three are in the back of the book. You might want to check that out as a resource.

I was at a talk Knuth gave a few years ago where he was discussing ZDDs and their algorithms, including how to do join. If you're interested, I believe that the lecture was recorded and should be online here.

Hope this helps!

like image 133
templatetypedef Avatar answered Sep 25 '22 02:09

templatetypedef