Finding the (k,l)-core of a tree network with unreliable edges

Document Type : Original Article

Authors

1 Department of Mathematics, Faculty of Science, Alexandria University, Alexandria, Egypt.

2 Department of Basic Sciences, Faculty of Engineering, Pharos University, Alexandria, Egypt.

Abstract

Given a reliable tree network  containing  vertices where each edge has an independent operational probability, this paper presents finding a reliable subtree with at most leaves and with a diameter of at most  which maximizes the expected number of nodes that are reachable from the selected subtree by operational paths. An efficient algorithm is presented for finding a reliable tree core of. Numerical example is explained to clarify the efficient algorithm.                                                                             

References

[1]      S. Peng, A.B. Stephens, Y. Yesha,” Algorithms for a core and a tree core of a tree”, J.  Algorithms Vol. 15, pp. 143-159, (1993).
[2]     A. Shioura and T. Uno, “Alinear time algorithm for finding a k-tree core”, J Algorithms, Vol. 23 pp. 281- 290, (1997).
[3]     R.I. Becker, I. Lari, G. Storchi, A. Scozzari, “Efficient algorithms for finding the core of tree networks”,  Networks Vol. 40(4), pp. 208-251, (2002).
[4]     B. Wang, S.Peng, H.Yu and S.Ku,” Efficient algorithms for a constrained k-tree core problem in a tree network”, Journal of Algorithms, Vol. 59, pp. 107-124, (2006).
[5]     J. Puerto, F. Ricca and A. Scozzari, “Reliability problems in multiple path-shaped facility location on networks”, Discrete Optimization, Vol. 12, pp. 61-72, (2014).
[6]     S. Peng, W. Lo, “Efficient algorithms for finding a core of a tree with a specified length”, J. Algorithms,Vol. 20, pp. 445-458, (1996).

Files

Share

How to cite

Statistics