CFP last date
21 October 2024
Reseach Article

An Algorithm for Enumeration of Terminal and Multi Terminal Paths in a Reliability Graph of Communication Networks

Published on December 2013 by Mohd Ashraf Saifi, Rajesh Mishra
ICST Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness
Foundation of Computer Science USA
QSHINE - Number 1
December 2013
Authors: Mohd Ashraf Saifi, Rajesh Mishra
3c5094cd-9105-414e-aa3f-c0c5d1181761

Mohd Ashraf Saifi, Rajesh Mishra . An Algorithm for Enumeration of Terminal and Multi Terminal Paths in a Reliability Graph of Communication Networks. ICST Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness. QSHINE, 1 (December 2013), 8-13.

@article{
author = { Mohd Ashraf Saifi, Rajesh Mishra },
title = { An Algorithm for Enumeration of Terminal and Multi Terminal Paths in a Reliability Graph of Communication Networks },
journal = { ICST Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness },
issue_date = { December 2013 },
volume = { QSHINE },
number = { 1 },
month = { December },
year = { 2013 },
issn = 0975-8887,
pages = { 8-13 },
numpages = 6,
url = { /proceedings/qshine/number1/14407-1305/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 ICST Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness
%A Mohd Ashraf Saifi
%A Rajesh Mishra
%T An Algorithm for Enumeration of Terminal and Multi Terminal Paths in a Reliability Graph of Communication Networks
%J ICST Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness
%@ 0975-8887
%V QSHINE
%N 1
%P 8-13
%D 2013
%I International Journal of Computer Applications
Abstract

The mathematical theory of reliability has grown out of the demand of modern technology and particularly out of the experience with complex systems. The main objective is to enhance the ability of such complex network systems. This work present an efficient algorithm, which is a novel approach to generate all the minimal paths of the general flow network based on the principle of backtracking. It is a general flow network because, the proposed approach can find the minimal paths for multiple sources and multiple sinks in the network. One can further evaluate the network reliability using any existing SDP (Sum of Disjoint Products) based approach.

References
  1. S. K. Chaturvedi and K. B. Misra 2002 "An efficient multivariable inversion algorithm for reliability evaluation of complex system using pathsets" International journal of reliability, quality, safety engineering, Vol. 9, No. 3 pp 237-259,
  2. Misra K. B. and T. S. M. Rao 1982"Reliability analysis of redundant network using flow graph " IEEE Transaction on Reliability, Vol. R-31, No. 2, pp. 174-176,
  3. Misra K. B. (Ed),1993 New Trends in System Relaibility Evaluation, Elsevier, Amsterdom.
  4. Gebre B. A. and J. E. Ramirez-Marquez, 2007,Element Substitution Algorithm for Genral Two-terminal Network Reliability Analyses, IIE Transaction, Vol. 39, No. 3, pp. 265-275.
  5. Misra K. B. , Relaibility, 1992, Analysis and Predection: A Methodology Oriented Treatment, Elsevier, Amsterdom.
  6. Wei-Chang Yeh, 2009, "A Simple Universal Generating Function Method to Search for all Minimal Paths in Network", IEEE Transactions on Systems, Vol. 39,No. 6,November.
  7. S. P. Jain and K. Gopal,1998 "An efficient algorithm for computing global reliability of a network", IEEE Transaction Reliability, Vol. 37,No. 5,pp. 488-492.
  8. H. Feng and S. P. Chang, 1998 "A method of Reliability evaluation for computer communication networks", IEEE International Symposium on Circuits and Systems,.
  9. M. A. Aziz, M. A Sobana and M. A Samad, 1992, "Reduction of Computations in enumeration of terminal and multiterminal path set by method of indexing", Microelectronics and Reliability, Vol. 32, No. 8.
  10. . C. Monticone, 1993 "An implementation of buzacott algorithm for network global reliability", IEEE Transaction Reliabiltiy, Vol. 42, No. 1.
  11. Smail Adjabi and Kahina Bouchama, 2011 "k-terminal reliability Evaluation of a Telecommunications Network represented by Discrete and a Dynamic model" International Journal of Operation Research Vol. 8, No. 3.
  12. Tong Luo and K. S Trivedi, 1998 "An improved algorithm for Coherent System Reliability", IEEE Transactions on Reliability, Vol. 47, No. 1.
  13. A. Satyanarayan and M. K Chang, 1983 "Network Reliability and Factoring theorem," Networks, vol. 13.
  14. R. K. Wood, 1986 "Factoring algorithm for computing k-terminal reliability", IEEE Transaction. Reliability, Vol. R-35.
  15. L. B. Page and J. E. Perry, 1989 "A practical implementation of factoring theorem", IEEE Transaction Reliability, vol. R-38, No. 5.
  16. L. B. Page and J. E. Perry, 1989, "Reliability analysis of directed networks using the factoring theorem", IEEE Transaction. Reliability, Vol. R-38, No. 5.
  17. O. R. Theologou and J. G. Carlier, 1991 "Factory and Reduction for networks with the imperfect nodes", IEEE Transactions Reliability, Vol. 40, No. 2.
  18. P. Ng Tony, 1991 "k-terminal Relaibility of hierarchical networks", IEEE Transactions Reliability, Vol. 40, No. 2.
  19. D. Rath and K. P. Somam, 1997 "A simple method for generating k-trees of a network," Microelectronics and Reliability, Vol. 46, No. 2.
  20. K. D. Heidtmann, 1989"Smaller sums of disjoint products by sub product inversion," IEEE Transactions Reliability, vol. R-38, no. 3, pp. 305-311.
  21. R. Mishra and S. K. Chaturvedi, 2009 "A Cutsets-Based Unified Framework to Evaluate Network Reliability Measures" IEEE Transaction on Reliability, Vol. 58, No. 4, pp. 658-666.
Index Terms

Computer Science
Information Sciences

Keywords

Path Sets Cutsets. Network Reliability Backtracking