To search, Click below search items.


All Published Papers Search Service


Fast Operations on Integer Set by Using OBDD


Guanfeng Lv, Kaile Su


Vol. 6  No. 5  pp. 116-119


Ordered Binary Decision Diagrams (OBDD) is a data structure mainly used for the representation and manipulation of Boolean functions as used in VLSI CAD systems. In this paper, we present operations (union, intersection, difference, symmetric-difference, complement, include) on integer set by using OBDD. When the maximum of an integer set is not too huge (less than 10,000,000), experimental results show that OBDD-based algorithms(union, intersection, difference, symmetric-difference) are faster than balanced trees (e.g., Red-Black Trees) and skip lists under most circumstances, though the latter two achieved the low bound of set operations. Meanwhile OBDD-based representation of integer set are space-saving. As an application of the operations algorithms, we use them into image processing.


OBDD, Data Structure, Set Operation, Image Processing