Parallel constructing of the shortest coverings of large Boolean matrices

• Autorzy: Novikov S.
• Języki publikacji: EN

Abstrakty

EN

The paper presents two options of the parallel algorithm for finding the shortest covering of a large Boolean matrix, where the decomposition of the initial matrix into matrices of smaller sizes is based on the partitioning of rows. The parallel algorithm COVMB contains sequential algorithms for partitioning of initial m × n Boolean matrix on submatrices, building special matrices, summering of the shortest coverings of special Boolean matrices with smaller sizes as well as the sequential algorithm SECNOP for finding the shortest coverings of smaller Boolean matrices.

Słowa kluczowe

EN

Boolean matrix; shortest covering; decomposition; sequential algorithm; parallel algorithm; cluster

• Wydawca: Wydawnictwo Uniwersytetu Przyrodniczo-Humanistycznego w Siedlcach
• Czasopismo: Studia Informatica : systems and information technology
• Rocznik: 2016
• Tom: Vol. 1-2(20)
• Strony: 27--37
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Novikov S.

• Institute of Mathematics and Computer Science, The John Paul II Catholic University of Lublin, Konstantynów Street 1H, 20-708 Lublin, Poland

Bibliografia

• 1. A. Zakrevskij, Yu. Pottosin, L. Cheremisinova. Combinatorial Algorithms of Discrete Mathematics. -Ed. A. Keevalik.- Tallin: TUT Press, 2008, 193 pages.
• 2. V.S. Ponomarenko, S.V. Listrovoj. Metod resheniya zadachi o minimal'nom pokrytii kak sredstvo planirovaniya v GRID. Problemy upravleniya. 2008, t. 3, pp. 78–84 (in Russian).
• 3. Leonchik P.V. Algoritm pokrytiya razrezhennyh bulevyh matric. Informatika, 2007, 2, pp. 53-61 (in Russian).
• 4. Novikov S.V. Rasparallelivanie vychislenij pri reshenii dvuh zadach postroeniya optimal'nyh pokrytij. Vestnik Grodnenskogo universiteta, Grodno, seriya 2, 1(92), 2010, pp. 30-36 (in Russian).
• 5. Adam Adamus. Równoległy program znalezienia minimalnego pokrycia macierzy Boole’a o dużych rozmiarach. Praca magisterska. Akademia Podlaska, Siedlce, 2010, 99 pages.
• 6. Sergey Novikov, Adam Adamus. Investigations of the efficiency of a parallel program for construction of the shortest covering of a Boolean matrix. Studia Informatica, Systemy i technologie informacyjne, VOLUME 1-2(14)2010, Wyd. UPH, Siedlce, 2011, pp. 67-76.
• 7. Adrian Nogal. Algorytm znalezienia minimalnego pokrycia macierzy Boole’a i implementacja równoległego programu na komputerze wysokiej wydajności. Praca dyplomowa inżynierska. Uniwersytet Przyrodniczo-Humanistyczny w Siedlcach, Siedlce, 2014, 40 pages.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).