Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
first previous next last
cannonical link button

http://yadda.icm.edu.pl:80/baztech/element/bwmeta1.element.baztech-bc606468-aba1-4f48-a1f5-6ec8b60ef015

Czasopismo

Elektrotechnika i Elektronika

Tytuł artykułu

Heurystyczny algorytm projektowania sieci elektroenergetycznej typu drzewo Steinera

Autorzy Schiff, K. 
Treść / Zawartość http://journals.bg.agh.edu.pl/ELEKTROTECHNIKA/
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   рrоblem 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
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-bc606468-aba1-4f48-a1f5-6ec8b60ef015
Identyfikatory