NDLI: A New and Efficient Approach Based on Binary Decision Diagram to Evaluate the K-terminal Reliability of Distributed Networks

Content Provider	IEEE Xplore Digital Library
Author	Panda, D.K. Dash, R.K.
Copyright Year	2013
Description	Author affiliation: Dept. of CSA, Coll. of Eng. & Technol., Bhubaneswar, India (Dash, R.K.) \|\| SOA Univ., Bhubaneswar, India (Panda, D.K.)
Abstract	This paper presents a new and efficient method based on binary decision diagram(BDD) to evaluate the K-terminal reliability of the distributed networks. Here the distributed network is modeled as a probabilistic graph G(V, E), where V is vertex set and E is the edge set. Two basic operation viz. contraction and deletion are used to make partitions the initial graph into the sub graphs. An efficient algorithm is proposed to make such partitions. Each partition is labeled by a partition string. Each of such partition string is inserted into a hash table in order to avoid duplicity. As the size of Binary Decision Diagram (BDD) is largely dependent on its ordering an efficient variable ordering is proposed. The Binary Decision Diagram(BDD) is constructed from the different partitions of the initial graph/sub graphs. In the algorithm only those partition of the graph/ sub graph are used for constructing the BDD that have no duplicity by using this variable ordering which is assured by searching the hash table. As in a BDD all the paths from the root to the leaves are disjoints, the probability of K-terminal connectivity is computed by traversing the BDD using Breadth first Search (BFS) method. For this computation of K-terminal reliability another algorithm is proposed which recursively compute the k-terminal reliability of the graph. The proposed method is well illustrated by taking a suitable example. The reliability of some important distributed networks such as Hypercube(HC), Twisted Hypercube(THC), Crossed cube(CC), Mesh, Torus are evaluated by the proposed method.
Starting Page	574
Ending Page	578
File Size	397457
Page Count	5
File Format	PDF
ISBN	9780769550138
DOI	10.1109/ICMIRA.2013.120
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-12-21
Publisher Place	India
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Binary decision diagram Boolean functions Network reliability Probabilistic graph Computer network reliability Binary decision diagrams Reliability theory
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in