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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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_a
15-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

Received: 07.12.2016
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}


Linking options:
  • http://mi.mathnet.ru/eng/ia492
  • http://mi.mathnet.ru/eng/ia/v11/i3/p113

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:97
    Full text:20
    References:12
    First page:3

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019