Call for Paper - November 2020 Edition
IJCA solicits original research papers for the November 2020 Edition. Last date of manuscript submission is October 20, 2020. Read More

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

Print
PDF
International Journal of Computer Applications
© 2011 by IJCA Journal
Number 1 - Article 1
Year of Publication: 2011
Authors:
Manoj Singhal
Dr. Girish Sharma
Dr. R. K. Chauhan
10.5120/3801-2502

Manoj Singhal, Dr. Girish Sharma and 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):1-8, October 2011. Full text available. BibTeX

@article{key:article,
	author = {Manoj Singhal and Dr. Girish Sharma and 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},
	year = {2011},
	volume = {31},
	number = {3},
	pages = {1-8},
	month = {October},
	note = {Full text available}
}

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.

Reference

  • 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.
  • M. O. Ball : Computational complexity of network reliability analysis: An overview : IEEE Trans. Reliability, vol. R-35, no. 3, pp. 230–239, 1986.
  • J. S. Provan : The complexity of reliability computations on planar and acyclic graphs : SIAM J. Computing, vol. 15, no. 3, pp. 694–702, 1986.
  • M. O. Locks : A minimizing algorithm for sum of disjoint products : IEEE Trans. Reliability, vol. R-36, no. 4, pp. 436–445, 1987.
  • 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.
  • 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.
  • 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.
  • J. P. Gadani : System effectiveness evaluation using star and delta transformations : IEEE Trans. Reliability, vol. R-30, no. 1, pp. 43–47, 1981.
  • O. Theologou and J. Carlier : Factoring and reductions for networks with imperfect vertices : IEEE Trans. Reliability, vol. R-40, pp. 210–217, 1991.
  • A. Satyanarayana and M. K. Chang : Network reliability and the factoring theorem :Networks, vol. 13, pp. 107–120, 1983.
  • R. K.Wood : A factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliability : Networks, vol. 15, pp. 173–190, 1985.
  • B. Akers : Binary decision diagrams :IEEE Trans. Computers, vol. C-27, pp.509–516, 1978.
  • R. E. Bryant : Symbolic Boolean manipulation with ordered binary-decision diagrams : ACM Computing Surveys, vol. 24, no. 3, pp. 293–318, 1992.
  • 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.
  • A. Rauzy : New algorithms for fault tolerant trees analysis : Reliability Engineering and System Safety, vol. 5, no. 59, pp. 203–211, 1993.
  • A. Rauzy : A new methodology to handle Boolean models with loops : IEEE Trans. Reliability, vol. R-52, no. 1, pp. 96–105, 2003.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • X. Zang, H. Sun, and K. S. Trivedi : A BDD-based algorithm for reliability Graph Analysis Technical Report
  • Online. Available: http://www.ee.duke.edu/~hairong/workinduke/relgrap.