RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Inform. Primen.: Year: Volume: Issue: Page: Find

 Inform. Primen., 2017, Volume 11, Issue 3, Pages 113–122 (Mi ia492)

On parallelization of asymptotically optimal dualization algorithms

E. V. Djukovaab, A. G. Nikiforovc, P. A. Prokofyeva

a Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
b M. V. Lomonosov Moscow State University, 1-52 Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation
c Technische University of Munich, 21 Arcisstrasse, Munich 80333, Germany

Abstract: The main goal of the paper is to develop and implement an approach to building efficient parallel algorithms for intractable enumeration problems and to apply this approach to one of the central enumeration problems, i. e., dualization. Asymptotically optimal algorithms for dualization are considered to be the fastest among the known ones. They have a theoretical justification of the efficiency on average. The size of enumerated set in the dualization problem grows exponentially with the size of the input; thus, parallel computations are reasonable to be utilized. The authors introduce the static parallelizing scheme for asymptotically optimal algorithms of dualization and present the results of the testing. Statistical processing of the experimental results is conducted in order to determine the kind of distribution of the random variables, representing the size of the subtasks for parallel computation. The conditions, under which the schema demonstrates almost maximum speedup and quite uniform processors load, are discovered.

Keywords: discrete enumeration problem; dualization; asymptotically optimal algorithm; irreducible covering of a Boolean matrix; polynomial-time delay algorithm; parallel dualization algorithm.

 Funding Agency Grant Number Russian Foundation for Basic Research 16-01-00445_a15-51-05059_Àðì_à The research was supported by the Russian Foundation for Basic Research (projects Nos. 16-01-00445-a and 15-51-05059).

DOI: https://doi.org/10.14357/19922264170313

Full text: PDF file (309 kB)
References: PDF file   HTML file

Language:

Citation: E. V. Djukova, A. G. Nikiforov, P. A. Prokofyev, “On parallelization of asymptotically optimal dualization algorithms”, Inform. Primen., 11:3 (2017), 113–122

Citation in format AMSBIB
\Bibitem{DyuNikPro17} \by E.~V.~Djukova, A.~G.~Nikiforov, P.~A.~Prokofyev \paper On parallelization of asymptotically optimal dualization algorithms \jour Inform. Primen. \yr 2017 \vol 11 \issue 3 \pages 113--122 \mathnet{http://mi.mathnet.ru/ia492} \crossref{https://doi.org/10.14357/19922264170313} \elib{http://elibrary.ru/item.asp?id=29992117}