International Journal of System & Software Engineering

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

An Algorithm for the Construction of Decision Diagram by Eliminating, Merging and Rearranging the Input Cube Set


Affiliations
1 Department of CSE, Vijaya Vittal Institute of Technology, Bangalore, Karnataka, India
2 Department of ECE, Vivekanada Institute of Technology, Bangalore, Karnataka, India
     

   Subscribe/Renew Journal


This proposed work is Decision Diagrams are a data structure that allows compact representation of discrete functions Boolean functions. The construction of DDS in terms of memory and time is considered as problems. We proposed method of eliminating, merging and reordering the set of cubes in matrix specification that results in the reduction of both memories occupied and time complexities of the construction of DDs. First we employ elimination algorithm followed by merging and then again elimination algorithm and reordering the set of cubes. In this way, the number of operations on the nodes is reduced. This reduction results in a decrease both in the number of temporary nodes and construction time the experiments show that the total number of created nodes is reduced on an average by 35% and construction time is decreased by 49%.

Keywords

Cubes, Decision Diagram
Subscription Login to verify subscription
User
Notifications
Font Size


  • Bryant, R. E. (1986). Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transaction on Computer, 35(8), 677-691.

  • Hubbard, P. M. (1990). Constructive Solid Geometry for Triangulated Polyhedral. Technical Report CS-90-07, Brown University.

  • Krishnan, S. & Manocha, D. (1997). Ancient surface intersection algorithm based on lower-dimensional formulation. ACM Transactions on Graphics, 16(1), 74-106.

  • Laidlaw, D. H., Trumbore, W. B. & Hughes, J. H. (1986). Constructive Solid Geometry for Polyhedral Objects: SIGGRAPH 86, Brown University (pp 161-170). New York, NY, USA: ACM Press.

  • Naylor, B., Amanatides, J. & Thibault, W. (1990). Merging BSP Trees Yields Polyhedral Set Operations. SIGGRAPH 90 (pp. 115-124). New York, NY, USA: AT&T Bell Laboratories, AC Press.

  • Rossignac, J. (2007). Solid and Physical Modeling. Wiley Encyclopedia of Electrical and Electronics Engineering.

  • Smith, J. & Dodgson, N. (2007). A topologically robust algorithm for Boolean operations on polyhedral shapes using approximate arithmetic. Computer Aided Design, 39(2), 149-163.

  • Tilove, R. V. (1980). Set Membership Classification: A United Approach to Geometric Intersection Problems. IEEE Transactions on Computers, 29(10), 874-883.


Abstract Views: 464

PDF Views: 4




  • An Algorithm for the Construction of Decision Diagram by Eliminating, Merging and Rearranging the Input Cube Set

Abstract Views: 464  |  PDF Views: 4

Authors

Manjunath Managuli
Department of CSE, Vijaya Vittal Institute of Technology, Bangalore, Karnataka, India
M. H Yogeshkumar
Department of ECE, Vivekanada Institute of Technology, Bangalore, Karnataka, India

Abstract


This proposed work is Decision Diagrams are a data structure that allows compact representation of discrete functions Boolean functions. The construction of DDS in terms of memory and time is considered as problems. We proposed method of eliminating, merging and reordering the set of cubes in matrix specification that results in the reduction of both memories occupied and time complexities of the construction of DDs. First we employ elimination algorithm followed by merging and then again elimination algorithm and reordering the set of cubes. In this way, the number of operations on the nodes is reduced. This reduction results in a decrease both in the number of temporary nodes and construction time the experiments show that the total number of created nodes is reduced on an average by 35% and construction time is decreased by 49%.

Keywords


Cubes, Decision Diagram

References