Nowy algorytm do szybkiego obliczania niezawodności sieci.

• Autorzy: Madeyski L. , Mazur Z.

Warianty tytułu

EN

New algorithm for fast computing of network reliability.

• Języki publikacji: PL

Abstrakty

EN

Network reliability analysis of complex system (including computer, telecomunication, transportation networks or electric networks has been a subject of intensive research for a long time. The problem of network reliability analysis using connectivity based reliability measures is considered in this paper. Such measures are justified since most networks employ dynamic routing so that trafic can be rerouted around failed links as long as a network remains connected. A propbabilistic undirected graph G=(V, E) with a distinguished subset of vertices K is used to a model K. The problem of computing K-terminal reliability of a network with a general structure is known to be NP-hard. It means that it is unlikely that there exists an algorithm which will find exactly optimal solution to all instances of the problem in time which is polynomial in the size of the imput. A new algorithm utilising the cache technique which is a modified technique of dynamic programming and suitable heuristic strategies of preserving labels order and problem decomposition have been presented in this paper. The algorythm has been implemented and has achived excellent performances.

Słowa kluczowe

PL

niezawodność sieci; algorytm

EN

network reliability; algorithm

• Wydawca: Komitet Budowy Maszyn PAN
• Czasopismo: Zagadnienia Eksploatacji Maszyn
• Rocznik: 1998
• Tom: Vol. 33, nr 3
• Strony: 391--404
• Opis fizyczny: Bibliogr. 20 poz., rys., tab.

Twórcy

autor

Madeyski L.

• Politechnika Wrocławska, Wydziałowy Zakład Informatyki, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław

autor

Mazur Z.

• Politechnika Wrocławska, Wydziałowy Zakład Informatyki, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław

Bibliografia

• [1] Politof, T., Satyanarayana, A.: Efficient algorithms for reliability analysis of planar networks - A survey. IEEE Trans. Reliability 1986 (35), 252-259.
• [2] Beichelt, F., Tittmann, P.: A Generalized reduction method for the connectedness probability of stochastic networks. IEEE Trans. Reliability 1991 (40), 198-204.
• [3] Beichelt, F., Tittmann, P.: Reliability analysis of communication networks by decomposition. Microelectron. Reliab. 1991 (31), 868-872.
• [4] Shier, D.R.: Network reliability and algebraic structures. Oxford University Press, New York 1991.
• [5] Ball, M.O.: Computational complexity of network reliability analysis: An overview. IEEE Trans. Reliability 1986 (R-35), 230-239.
• [6] Ball, M.O., Provan, J.S.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comp. 1983 (12), 777-788.
• [7] Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Computing 1979 (8), 410-421.
• [8] Page, L.B., Perry, J.G.: A practical implementation of the factoring theorem for network reliability. IEEE Trans. Reliability 1988 (37), Aug., 259-267.
• [9] Wood, R.K.: Factoring algorithms for computing K-terminal network reliability. IEEE Trans. Reliability 1986 (R-35), 269-278.
• [10] Wood, R.K.: Factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliability. Networks 1985 (15), 173-190.
• [11] Resende, M.G.C.: A program for reliability evaluation of undirected networks via polygon-to-chain reductions. IEEE Trans. Reliability 1986 (35), Apr., 24-29.
• [12] Resende, L.I.P.: Implementation of factoring algorithm for reliability evaluation of undirected networks. IEEE Trans. Reliability 1988 (37), Dec., 462-468.
• [13] Wood, R.K.: Triconnected decomposition for computing K-terminal network reliability. Networks 1989 (19), 203-220.
• [14] Carlier, J., Lucet, C.: A decompositoin algorithm for network reliability evaluation. Discrete Appl. Math. 1996, 141-156.
• [15] Moskowitz, C.: The analysis of redundancy networks. AIEE Trans. Commun. electron. 1958 (39), 627-632.
• [16] Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to algorithms. MIT Press, 1994.
• [17] Sedgewick, R.: Algorithms in C. Addison-Wesley, 1990.
• [18] Wróblewski, P.: Algorytmy, struktury danych i techniki programowania. Helion, 1997.
• [19] Banachowski, L., Diks, K., Rytter, W.: Algorytmy i struktury danych. WNT, 1996.
• [20] Aho, A.V., Hopcroft, J.E., Ullman, J.D.: Projektowanie i analiza algorytmów komputerowych. PWN, 1983.