×

A linear time algorithm for computing the most reliable source on a series–parallel graph with unreliable edges. (English) Zbl 0915.68081

Summary: Given a network with n vertices and m edges where each edge has an independent operational probability, we are interested in finding a vertex of the network whose expected number of reachable vertices is maximum. Such a vertex is called a most reliable source of the network. This problem was studied by E. Melachrinoudis and M. E. Helander [Networks 27, No. 3, 219-237 (1996; Zbl 0851.90074)] where an \(O(n^{2})\) time algorithm was proposed when the given network is a tree. In a more recent paper, Xue presented an \(O(n)\) time algorithm for this problem when the given network is a tree. In this paper, we present an \(O(n)\) time algorithm for computing the most reliable source on series-parallel graphs, using their embeddings in 2-trees.

MSC:

68W10 Parallel algorithms in computer science

Citations:

Zbl 0851.90074
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows: Theory, Algorithms and Applications (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1201.90001
[2] Ball, M. O.; Lin, F. L., A reliability model applied to emergency service vehicle location, Oper. Res., 41, 18-36 (1993) · Zbl 0775.90264
[3] Ball, M. O.; Provan, J. S.; Shier, D. R., Reliability covering problems, Networks, 21, 345-357 (1991) · Zbl 0738.90035
[4] Batta, R.; Dolan, J. M.; Krishnamurthy, N. N., The maximal expected covering location problem: Revisited, Transportation Sci., 23, 277-287 (1989) · Zbl 0692.90040
[5] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan: Macmillan London · Zbl 1134.05001
[6] Colboura, C. J., The Combinatorics of Network Reliability (1987), Oxford University Press: Oxford University Press New York
[7] Daskin, M. S., A maximum expected covering location model: Formulation, properties and heuristic solution, Transportation Sci., 17, 48-70 (1983)
[8] Eiselt, H. A.; Gendreau, M.; Laporte, G., Location of facilities on a network subject to a single-edge failure, Networks, 22, 231-246 (1992) · Zbl 0766.90052
[9] Farley, A. M., Networks immune to isolated failures, Networks, 11, 255-268 (1981) · Zbl 0459.94036
[10] Melachrinoudis, E.; Helander, M. E., A single facility location problem on a tree with unreliable edges, Networks, 27, 219-237 (1996) · Zbl 0851.90074
[11] Mirchandani, P. B., The \(p\)-median problem and generalizations, (Mirchandani, P. B.; Francis, R. L., Discrete Location Theory (1990), Wiley: Wiley New York) · Zbl 0731.90050
[12] Mirchandani, P. B.; Odoni, A. R., Locations of medians on stochastic networks, Transportation Sci., 13, 85-97 (1979)
[13] Nel, L. D.; Colbourn, C. J., Locating a broadcast facility in an unreliable network, INFOR, 28, 363-379 (1990) · Zbl 0718.90052
[14] ReVelle, C.; Hogan, K., The maximum availability location problem, Transportation Sci., 23, 192-200 (1989) · Zbl 0681.90036
[15] Rose, D. J., On simple characterizations of \(k\)-trees, Discrete Math., 7, 317-322 (1974) · Zbl 0285.05128
[16] Shier, D. R., Network Reliability and Algebraic Structures (1991), Oxford University Press: Oxford University Press New York · Zbl 0729.90033
[17] Shilling, D. A.; Jayaraman, V.; Barkhi, R., A review of covering problems in facility location, Location Sci., 1, 25-55 (1993) · Zbl 0923.90108
[18] Wald, J. A.; Colbourn, C. J., Steiner trees, partial 2-trees, and minimum IFI networks, Networks, 13, 159-167 (1983) · Zbl 0529.68036
[19] Weaver, J. R.; Church, R. L., Computational procedures for location problems on stochastic networks, Transportation Sci., 17, 168-180 (1983)
[20] G.L. Xue, Linear time algorithms for computing the most reliable source on an unreliable tree network, Networks, accepted for publication.; G.L. Xue, Linear time algorithms for computing the most reliable source on an unreliable tree network, Networks, accepted for publication. · Zbl 0887.68003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.