Finding the (k,l)-core of a tree network with unreliable edges | ||||
| Menoufia Journal of Electronic Engineering Research | ||||
| Article 14, Volume 29, Issue 1, January 2020, Page 98-104 PDF (1.06 MB) | ||||
| Document Type: Original Article | ||||
| DOI: 10.21608/mjeer.2020.69193 | ||||
 View on SCiNiTO | ||||
| Authors | ||||
| Abdallah W. Aboutahoun1; Eman Fares2 | ||||
| 1Department of Mathematics, Faculty of Science, Alexandria University, Alexandria, Egypt. | ||||
| 2Department 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). | ||||
|
Statistics Article View: 199 PDF Download: 168 |
||||
