CFP last date
22 April 2024
Call for Paper
May Edition
IJCA solicits high quality original research papers for the upcoming May edition of the journal. The last date of research paper submission is 22 April 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Article:A New Approach for Finding the various Optimal Variable Ordering to Generate the Binary Decision Diagrams (BDD) of a Computer Communication Network

by Manoj Singhal, Dr. Girish Sharma, Dr. R. K. Chauhan
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 31 - Number 3
Year of Publication: 2011
Authors: Manoj Singhal, Dr. Girish Sharma, Dr. R. K. Chauhan
10.5120/3801-2502

Manoj Singhal, Dr. Girish Sharma, Dr. R. K. Chauhan . Article:A New Approach for Finding the various Optimal Variable Ordering to Generate the Binary Decision Diagrams (BDD) of a Computer Communication Network. International Journal of Computer Applications. 31, 3 ( October 2011), 1-8. DOI=10.5120/3801-2502

@article{ 10.5120/3801-2502,
author = { Manoj Singhal, Dr. Girish Sharma, Dr. R. K. Chauhan },
title = { Article:A New Approach for Finding the various Optimal Variable Ordering to Generate the Binary Decision Diagrams (BDD) of a Computer Communication Network },
journal = { International Journal of Computer Applications },
issue_date = { October 2011 },
volume = { 31 },
number = { 3 },
month = { October },
year = { 2011 },
issn = { 0975-8887 },
pages = { 1-8 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume31/number3/3801-2502/ },
doi = { 10.5120/3801-2502 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:17:08.373428+05:30
%A Manoj Singhal
%A Dr. Girish Sharma
%A Dr. R. K. Chauhan
%T Article:A New Approach for Finding the various Optimal Variable Ordering to Generate the Binary Decision Diagrams (BDD) of a Computer Communication Network
%J International Journal of Computer Applications
%@ 0975-8887
%V 31
%N 3
%P 1-8
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In this paper we have adopted a new approach for finding the various optimal ordering to generate the binary decision diagrams of a computer communication network. We have shown that these binary decision diagrams are of minimum size and take same time to generate. If two binary decision diagrams have the same size and representing the same Boolean function, then these binary decision diagrams are known as dual binary decision diagrams, because they are dual of each other. We have also shown that the reliability obtained from these dual binary decision diagrams is equal by applying Shannon’s decomposition.

References
  1. C. Lucet and J.-F. Manouvrier : Exact methods to compute network reliability: in Statistical and Probabilistic Models in Reliability : D. C. Ionescu and N. Limnios, Eds. Birkhauser Boston, pp. 279–294, 1999.
  2. M. O. Ball : Computational complexity of network reliability analysis: An overview : IEEE Trans. Reliability, vol. R-35, no. 3, pp. 230–239, 1986.
  3. J. S. Provan : The complexity of reliability computations on planar and acyclic graphs : SIAM J. Computing, vol. 15, no. 3, pp. 694–702, 1986.
  4. M. O. Locks : A minimizing algorithm for sum of disjoint products : IEEE Trans. Reliability, vol. R-36, no. 4, pp. 436–445, 1987.
  5. S. Hariri and C. S. Raghavendra : SYREL: A symbolic reliability algorithm based on path and cut set methods : IEEE Trans. Computers, vol. C-36, no. 10, pp. 1224–1232, 1987.
  6. S. H. Ahmad : Simple enumeration of minimal cut sets of acyclic directed graph : IEEE Trans. Reliability, vol. R-27, no. 5, pp. 484–487, 1988.
  7. M. S. Choi and C. H. Jun : Some variant of polygon-to-chain reductions in evaluating reliability of undirected network : Microelectron. Reliab., vol. 35, no. 1, pp. 1–11, 1985.
  8. J. P. Gadani : System effectiveness evaluation using star and delta transformations : IEEE Trans. Reliability, vol. R-30, no. 1, pp. 43–47, 1981.
  9. O. Theologou and J. Carlier : Factoring and reductions for networks with imperfect vertices : IEEE Trans. Reliability, vol. R-40, pp. 210–217, 1991.
  10. A. Satyanarayana and M. K. Chang : Network reliability and the factoring theorem :Networks, vol. 13, pp. 107–120, 1983.
  11. R. K.Wood : A factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliability : Networks, vol. 15, pp. 173–190, 1985.
  12. B. Akers : Binary decision diagrams :IEEE Trans. Computers, vol. C-27, pp.509–516, 1978.
  13. R. E. Bryant : Symbolic Boolean manipulation with ordered binary-decision diagrams : ACM Computing Surveys, vol. 24, no. 3, pp. 293–318, 1992.
  14. O. Coudert and J. C. Madre : Implicit and incremental computation of primes and essential primes of Boolean functions : in Proc. of the 29th ACM/IEEE Design Automation Conference, 1992, pp. 36–39.
  15. A. Rauzy : New algorithms for fault tolerant trees analysis : Reliability Engineering and System Safety, vol. 5, no. 59, pp. 203–211, 1993.
  16. A. Rauzy : A new methodology to handle Boolean models with loops : IEEE Trans. Reliability, vol. R-52, no. 1, pp. 96–105, 2003.
  17. H. Imai, K. Sekine, and K. Imai : Computational investigations of all terminal network reliability via BDDs : IEICE Transactions on Fundamentals, vol. E82-A, no. 5, pp.714–721, 1999.
  18. Manoj Singhal, R. K. Chauhan, Girish Sharma, “An alternate approach to compute the reliability of a computer communication network using Binary Decision Diagrams”, Communications in Computer and Information Science, pp. 160-170, IC3 2010, Springer-Verlag Berlin Heidelberg 2010.
  19. F. Yeh, S. Lu, and S. Kuo : OBDD-based evaluation of k-terminal network reliability : IEEE Trans. Reliability, vol. R-51, no. 4, pp. 443-451, 2002.
  20. Manoj Singhal, R. K. Chauhan, Girish Sharma : Effects of Variable Ordering on Binary Decision Diagrams for Computation of Reliability of a Computer Communication Network : Journal of Computer Science, Vol. 4, issue 6, pp. 1837-1845, Sep-Oct 2010.
  21. Manoj Singhal, R. K. Chauhan, Girish Sharma : A New Optimal Approach for evaluating the size of BDD (Binary Decision Diagram) for calculating the Reliability of a CCN (Computer Communication Network) : International Journal of Advanced Networking and Applications, Vol. 1, issue 4, pp. 230-235, Jan-Feb 2010.
  22. S. J. Friedman and K. J. Supowit : Finding an optimal variable ordering for binary decision diagrams : IEEE Trans. Computers, vol. C-39, no. 5, pp. 710–713, 1990.
  23. Manoj Singhal, R. K. Chauhan, Girish Sharma : Network Reliability Computation using Different Binary Decision Diagrams: International Journal of Distributed and Parallel Systems, Vol. 1, No. 1, pp. 82-91, September 2010.
  24. Manoj Singhal, R. K. Chauhan, Girish Sharma : Use of Modified Binary Decision Diagrams in Reliability Evaluation of a Directed Computer Communication Network : The Icfai University Journal of Computer Sciences, Vol. III No. 3, pp. 22-30, July 2009.
  25. S. Kuo, S. Lu, F. Yeh : Determining terminal pair reliability based on edge expansion diagrams using OBDD : IEEE Trans. Reliability, Vol. 48, no. 3, pp. 234-246, 1999.
  26. G. Hardy, C. Lucet, and N. Limnios : Computing all-terminal reliability of stochastic networks with binary decision diagrams : in Proc.11th International Symposium on Applied Stochastic Models and Data Analysi, 2005, pp. 1468-1473.
  27. X. Zang, H. Sun, and K. S. Trivedi : A BDD-based algorithm for reliability Graph Analysis Technical Report
  28. Online. Available: http://www.ee.duke.edu/~hairong/workinduke/relgrap.
Index Terms

Computer Science
Information Sciences

Keywords

Binary Decision Diagrams (BDD) Directed Acyclic Graph (DAG) Computer communication Network (CNN) Dual Binary Decision Diagrams (DBDD) Ordered Binary Decision Diagrams (OBDD)

Powered by PhDFocusTM