International Journal of Advanced Networking and Applications

Open Access Open Access  Restricted Access Subscription Access

Binary Decision Diagrams and Its Variable Ordering for Disjoint Network


Affiliations
1 Department of Information Technology, Accurate Institute of Management and Technology, Greater Noida (U.P.), India
2 Department of Computer Applications, Bhai Parmanand Institute of Business Studies, New Delhi, India
3 Departement of Computer Science and Applications, Kurukshetra University, Kurukshetra, India
 

We know that binary decision diagram is a data structure that is used to store a Boolean function. They are used to find out the terminal reliability of a computer communication network. To generate the binary decision diagram of a given computer communication network, we need to order the edges of the given computer communication network because the size of the binary decision diagram is dependent on the ordering of the variables (edges). There are three types of variable ordering; optimal, good and bad ordering. Optimal ordering are those ordering which generate minimum size binary decision diagram. In this paper we have shown that if a directed computer communication network has m disjoints min-paths then m! optimal variable orderings exist to generate the binary decision diagrams of the given computer communication network.

Keywords

Binary Decision Diagrams (BDD), Computer communication Network (CNN), Directed Acyclic Graph (DAG), Modified Binary Decision Diagrams (MBDD).
User
Notifications
Font Size

Abstract Views: 107

PDF Views: 4




  • Binary Decision Diagrams and Its Variable Ordering for Disjoint Network

Abstract Views: 107  |  PDF Views: 4

Authors

Manoj Singhal
Department of Information Technology, Accurate Institute of Management and Technology, Greater Noida (U.P.), India
Girish Sharma
Department of Computer Applications, Bhai Parmanand Institute of Business Studies, New Delhi, India
R. K. Chauhan
Departement of Computer Science and Applications, Kurukshetra University, Kurukshetra, India

Abstract


We know that binary decision diagram is a data structure that is used to store a Boolean function. They are used to find out the terminal reliability of a computer communication network. To generate the binary decision diagram of a given computer communication network, we need to order the edges of the given computer communication network because the size of the binary decision diagram is dependent on the ordering of the variables (edges). There are three types of variable ordering; optimal, good and bad ordering. Optimal ordering are those ordering which generate minimum size binary decision diagram. In this paper we have shown that if a directed computer communication network has m disjoints min-paths then m! optimal variable orderings exist to generate the binary decision diagrams of the given computer communication network.

Keywords


Binary Decision Diagrams (BDD), Computer communication Network (CNN), Directed Acyclic Graph (DAG), Modified Binary Decision Diagrams (MBDD).