Heurystyczny algorytm projektowania sieci elektroenergetycznej typu drzewo Steinera

• Autorzy: Schiff K.

Warianty tytułu

EN

Heurystic algorithm for energy Steiner network design

• Języki publikacji: PL

Abstrakty

PL

W artykule tym zaprezentowano algorytm wyznaczania drzewa Steinera о złożoności obliczeniowej rzędu О(n3) bazujący na algorytmie Warshalla-Floyda wyznaczania najkrótszych ścieżek pomiędzy wszystkimi wierzchołkami grafu i nа algorytmie Sollina rozpinania drzewa о minimalnej wadze nа wierzchołkach grafu. Pojęcie punktów Steinera zostało jednak zmodyfikowane, gdyż w ich skład oprócz wierzchołków, które muszą znaleźć się w rozwiązaniu, dołączono w trakcie działania algorytmu wierzchołki, którе nie musiały znaleźć się w rozwiązaniu zgodnie z początkowymi założeniami.

EN

In this paper algorithm for Steineг tree network design with time complexity О(n3) is presented, which is based оn Warshall—Floyd shortes path algorithms and Sollin spaning trees algorithms, but the notion of Steiner point is modificated.

Słowa kluczowe

PL

drzewo Steinera; algorytm grafowy; problem NP-zupełny

EN

Steiner trees; graph algorithm; NP-complet problem

• Wydawca: Wydawnictwa AGH
• Czasopismo: Elektrotechnika i Elektronika
• Rocznik: 2001
• Tom: T. 20, z. 2
• Strony: 97--99
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Schiff K.

• Instytut Automatyki, Politechnika Krakowska

Bibliografia

• [1] Kulczycki J.: Optymalizacja struktur sieci elektroenergetycznych. Warszawa, WNT 1990
• [2] Коu L., Markowsky G., Berman L.: А fast algorithm for Steiner Trees. Acta Informatica, 15, 1981, 141-145
• [3] Mehlhorn K.: А faster approximation algorithm for Steiner problem in graphs. International Processing Letters, 27, 1988, 125-128
• [4] Wu Y.F., Widmayer Р., Wong С.K.: А faster approximation algorithm for the Steiner problem in graphs. Acta Informatica, 23, 223-229
• [5] Garey M.R., Johnson D.S.: Computers and Intractability. San Francisco, Freeman 1979
• [б] Hakimi S.L.: Steiner problem in graphs and its implications. Networks, 1, 1971, 113-133
• [7] Lawler E.L.: Combinatorial Optimization: Networks and Matroids. New York, Holt, Reinhalt and Winston 1976
• [8] Melzak Z.A.: Оn the problem of Steiner. Canad. Math. Вull., 4, 1961, 143-148
• [9] Dreyfus S.E., Wagner R.A.: The Steiner problems in graphs. Network, 1, 1971, 195-271
• [10] Winter. Н.: Steiner problems in networks: а surveу. Networks, 20, 1990, 109-120
• [11] Takahashi Н., Matsuyama А.: Аn approximate solution for the Steiner problem in graphs. Mach. Japonica, 24, 1980, 573-577
• [12] El-Arbi С.: Une heuristique роur lе рrоblеmе dе l'arbre dе Steiner. RAIRO Operation Research, 12, 1978, 207-212