Czasopismo
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Warianty tytułu
Algorithm for finding one and two elements minimal cuts in undirected graph
Języki publikacji
Abstrakty
Opracowano nowy algorytm znajdowania jedno- i dwu-elementowych minimalnych przekrojów w grafie o krawędziach nieskierowanych. Algorytm wykorzystuje unikalną metodę przeszukania grafu. W trakcie znajdowania przekrojów jednoelementowych są wyznaczane podgrafy, w których nie istnieją żadne przekroje jednoelementowe. Podgrafy te są następnie poddawane unikalnej metodzie przeszukania. Jest znajdowany podział grafu na te obszary, gdzie każda z krawędzi tworzy przynajmniej jeden przekrój dwuelementowy oraz te obszary, gdzie żadna z krawędzi nie wchodzi w skład jakiegokolwiek przekroju. Obszary grafu, w których krawędzie wchodzą w skład przekrojów, są używane do konstrukcji pełnego zbioru minimalnych przekrojów dwuelementowych.
A new algorithm for finding one and two elements cuts in undirected graph was given. The algorithm is based on an unique method for searching the graph. During the finding of one element cuts such subgraphs are found, in which there are no one element cut. These subgraphs are then searched separately by an unique method. A division of the graph into areas is found. One type of the area is such that each edges in it is in at least one minimal two elements cut. The second type is such that not any edge is in a minimal two elements cut. Areas of the graph where edges are in cuts are used to construct the full set of two elements minimal cuts.
Rocznik
Tom
Strony
131-150
Opis fizyczny
Bibliogr. 10 poz.
Twórcy
autor
- Instytut Informatyki, Politechnika Częstochowska, l_piatek@el.pcz.czest.pl
Bibliografia
- 1. Billinton R., Allan. R.: Reliability Evaluation of Engineering Systems, 2nd ed. Plenum Press, New York 1992.
- 2. Grabski F., Jaźwiński J.: Funkcje o losowych argumentach w zagadnieniach niezawodności, bezpieczeństwa i logistyki. WKŁ, Warszawa 2009.
- 3. Piątek Ł.: Algorytm znajdowania przekrojów w grafie o krawędziach niezorientowanych. Kwartalnik „Elektryka" 2010 z. 1, s. 53-64.
- 4. Grishkevich A.A.: Kombinatornye metody issledovanija ekstremalnych struktur matematiceskich modelej elektriceskich cepej i sistem. Izd. SUSU: Chelyabinsk 2004.
- 5. Grishkevich A.A.: Algorytm przeliczania dwuelementowych minimalnych przekrojów grafu skierowanego. „Informatyka Teoretyczna i Stosowana" 2006, R 6. nr 10, s. 85-100.
- 6. Grishkevich A., Piątek Ł.: Algorithm and Program for Finding Minimal and Quasi-Minimal Custs in Graphs. Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej 2008, nr 25, s. 49-52.
- 7. Ford L., Fullkerson D.: Flows in Networks, Princeton University Press. New Jork 1962
- 8. Stroustrup B.: Język C++. WNT, Warszawa 2002.
- 9. Billinton R., Lian. G.: A new technique for active minimal cut set selection used in substation reliability evaluation. "Journal of Microelectronics and Reliability" 1995, Vol. 35, No. 5, p. 797-805.
- 10. Piątek Ł.: Analiza niezawodności sieci sensorowych i akcyjnych. Kwartalnik „Elektryka" 2010, z. l,s. 61-68.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL3-0024-0010